ソートされないカード

ソートされないカード

締め切りが 2016/12/06 10:00 AM なので，その 1 分後に投稿されるように予約

設問
1〜n までの整数が1つずつ書かれている n 枚のカードを横一列に並べます。
カードを左から順に一枚ずつ見て、書かれている数字が i なら、左から i 番目のカードと交換する、
という作業を右端のカードまで繰り返します。

例えば、3, 2, 5, 4, 1の順に並んでいると、
最初のカードは 3 なので3番目のカードである 5 と交換し、5, 2, 3, 4, 1となります。
次のカードは 2 なので2番目のカードと交換（交換は発生しない）、
その次のカードは 3 なので3番目のカードと交換（交換は発生しない）、
その次のカードは 4 なので4番目のカードと交換（交換は発生しない）、
その次のカードは 1 なので1番目のカードである 5 と交換し、
1, 2, 3, 4, 5となり、昇順に並べ替えられます。
※カードは常に左から順番に見ていきます

右端まで処理した結果、書かれている数字が昇順に並ばない初期配置が何通りあるかを求めます。

標準入力から n が与えられるとき、書かれている数字が昇順に並ばない初期配置が何通りあるかを求め、
標準出力に出力してください。
例えば、n = 4 のとき、24通り中、以下の3通りがありますので、サンプルのように出力します。

2, 3, 4, 1
3, 4, 2, 1
4, 3, 1, 2
（n は最大で8とします。余裕がある人は、もう少し大きな n についても考えてみてください。）

【入出力サンプル】
標準入力
4

標準出力
3

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ブルートフォースでは，n=8 の場合に実行時間制限（1秒）に引っかかるのだが，細々したところをチューンアップして，なんとかねじ込んだ。

f = function(n) {
    z = matrix(1)
    if (n == 1) {
        cat(0)
    } else {
        for (i in 2:n) {
            x = cbind(z, i)
            a = c(1:i, 1:(i - 1))
            z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
            z[1:nrow(x), ] = x
            for (j in 2:i - 1) {
                z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
            }
        }
        cat(sum(apply(z, 1, function(x) {
            for (i in seq_along(x)) {
                if (i != x[i]) {
                    t = x[i]
                    x[i] = x[t]
                    x[t] = t
                }
            }
            any(x != 1:n)
        })))
    }
}

f(3) # 0
f(4) # 3
f(5) # 35
f(6) # 325
f(7) # 2989
f(8) # 28630