私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ソートされないカード」（CodeIQ）を参照してください。
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
Rubyで解答しています。
#!/usr/bin/ruby
def swap(arr)
for i in 0...arr.size
buf = arr[i]
if i != buf then
arr[i] = arr[buf]
arr[buf] = buf
end
end
for i in 0...arr.size
if i != arr[i] then return 1 end
end
return 0
end
def solve(n)
cnt = 0
(0...n).to_a.permutation{|arr|
cnt += swap(arr)
}
return cnt
end
while line = gets
line.strip!
if line.empty? then next end
p solve(line.to_i)
end
私のプログラムは簡単です。
しかし総当たりなので遅いです。多分、もっと頭の良い方法があります。
全てのカードの並びはn!パターンあります。
問題ではカードは1〜ですが、0〜にしてしまいます。そうすると、
[3, 2, 5, 4, 1] → [2, 1, 4, 3, 0]
になりますが、並び順のパターンを数えるのには関係ありません。
このようにして配列の要素をその値の要素番号の位置を入れ替えるという処理をすれば問題の通りの並び替えができます。
これを全パターンに対してやってみて、ソートできなかったものをカウントすれば良いわけです。
入力値を数値に変換し、solve()に渡します。
solve()が結果を返すのでそれを印字して終わります。
引数は入力値です。
Array#permutation()で全パターン列挙します。
その各パターンをswap()でソートできるかチェックします。swap()はソートできたら0、できなかったら1を返すので結果を加算してゆけば答えになります。
引数arrは数値の配列です。
先頭から順番に値を見て、値をその要素番号の値を入れ替えます（4〜10行目）。
並べ終わったら要素番号と値が一致しているかチェックし、異なる場所があれば1を返します（12〜14行目）。
全部一致していたら0を返します。
計算量を見積もったらn=8だと総当たりで余裕だったので何も考えず総当たりにしてしまいました(^^;。