ソートの交換回数の最小化(Ruby)
アルゴリズム・パズルです。
問題:
例えば 1~3 の数字が任意に並んだ 3桁の数字を、各桁の入れ替えによってソートする場合、その入れ替えの数が最小になるようにソートしたとします。たとえば 231 なら 231→132→123 で 2回の入れ替えになります。これをすべての順列において行い、入れ替え数の合計を出します。例えば 1~3 の場合なら、最小の入れ替え数の合計は 7回になります。
さて、これを 1~7 の 7桁の場合において求めて下さい。
Ruby で解いてみました。
q46.rb
h = {"1234567" => 0} queue =[["1234567", 0]] while (x = queue.shift) st, depth = x [*0..6].combination(2) do |i, j| st1 = st.dup st1[i], st1[j] = st1[j], st1[i] next if h[st1] h[st1] = depth + 1 if h.size == 5040 puts h.values.inject(:+) #=>22212 exit end queue.push([st1, depth + 1]) end end
求める最小の入れ替え数の合計は 22212回になります。かかった時間は僕の環境で 0.1秒あまりです。
ソートの目標の "1234567" から出発して、すべての入れ替えを行い、深さを 1ずつ増やしていって最終的にすべてのパターン(7! = 5040 とおり)があらわれるまで繰り返します。そして、最後に合計数を求めます。
ただこれ、幅優先探索で正解が求められるのですが、深さ優先にするとダメなのですよね。どうしてなのかいまひとつよくわからないのが恥ずかしい…。
いや、当り前か。いきなり深く潜ったらもっと早く出ている筈のパターンが深くなってしまうか。
ちなみに、深さの最大値は 6 です。これは考えてみたら当然ですね。7桁なら最大 6回入れ替えればソートできると。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (8件) を見る