プロジェクトオイラーProblem24を解いてみる
Problem 24 「辞書式順列」 †
順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である.
すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると
012 021 102 120 201 210 になる。
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?
この問題、結論から言うと
nums = [0,1,2,3,4,5,6,7,8,9]
p nums.permutation(10).to_a[999999].join
これで終わり。
Rubyには超優秀なpermutationというメソッドがあり、レシーバーに配列、引数にnサイズを渡してあげると全てのサイズnの大きさの順列を全て生成してくれるので、その配列の中から999999番目(配列のindexで考えて)を指定してあげるだけ。
実行速度が遅いのが気になる。
time ruby problem24.rb +
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
※下に説明するコード以外にもコメントで高速化のアイデアを教えていただきました。
nums = [0,1,2,3,4,5,6,7,8,9]
p nums.permutation(10).lazy.drop(999999).first.join
この問題の解答速度を高速化したい！
こちらの記事で同問題の高速化について言及しているのを発見
しかし、私は初見ではこのコードで何を行っているのか理解できなかったため、私自身の復習のために解説します。
理解に誤りがあれば教えていただけると幸いです。
まず、私なりに解釈して書いたコードがこちら。元記事と概ね同じです。
class Array
nums = [0,1,2,3,4,5,6,7,8,9]
n = 100_0000
def factorial(n)
if n == 1
return 1
elsif n == 0
return 1
end
return n * factorial(n - 1)
end
def perm_count(n)
n -= 1
arr = self
ans = []
while !arr.empty?
a = factorial(arr.size - 1)
m,n = n.divmod(a)
ans << (arr.delete_at(m))
end
return ans
end
puts nums.perm_count(n).join
end
元の記事では(arr.size - 1).permutation_sizeと言う記述が出てくるのですが、このpermutation_sizeはどうやら自作メソッドのようでした。
私の場合もfactorialメソッドを作成し、代用しています。
それでは説明していきます。
1.perm_count関数内でまず変数を準備
・n番目をインデックスとして使用するために-1します。
・numsで作成した配列をこの後、破壊的に変更していくのでarr配列を用意します。
・戻り値用に空のans配列を用意します。
2.perm_count関数内のwhile文１ループ目
・arr配列の要素を削除していくので[]の状態になるまでループを継続。
・a = factorial(arr.size - 1)
factorial関数は引数の「階乗」を求める。
ここで求めているのは先頭の数字を固定した際の、後に続く数字の組み合わせの数。
例）
[0,1,2,3]の4つの数字の順列を求める際、
0から始まる数字は3!通りあります。
1から〜、2から〜、３〜からの場合も同様。
・m,n = n.divmod(a)
配列中の先頭の数字は、a通りずつ変わっていくのでn / aの結果はarr配列の何番目の数字が今先頭にあるのかを示してくれます。
例)
arr = [0,1,2,3]
arr.permutation.to_a
=>
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1],
[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0],
[2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0],
[3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
arr配列のサイズ4に対して、3! = 6通りずつ[0]の数字が変わります。
例えば10番目は (10-1)/3! なので 1余り3ですね。
0から始まる数字のグループを[0],1から始まる数字のグループを[1]と捉えると、これは`arr配列`の[1]を指しているのと同義と分かります。
この例においては
arr = [0,1,2,3]ですから、10番目の数字の一文字目はarr[1] = 1です。
確かに上の一覧で確認すると10番目は[1,2,3,0]なので正しいと言えそうです。
これでans[0]の数字が決まりました。
・n = n / aの余り
この時この余りが示すのは同じ数字から始まる物だけ集めた配列の中でのn番目を示します。
具体的には
[[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0]]
この、1から始まる数字の配列の[3]を示します。
・ans << (arr.delete_at(m))
mには確定した先頭の数字のarr配列におけるインデックスが入っています。
確定した数字をans配列に代入すると同時に、arr配列を破壊的に変更しています。
ans = []
arr [0,1,2,3]
⬇️
ans << arr.delete_at(1)
⬇️
ans = [1]
arr = [0,2,3]
3.perm_count関数内のwhile文2ループ目以降
2.の処理を繰り返します。
ans[0]が確定したらans[1]の数字を特定、[2],[3],,,,と続いていきます。
最後にはarr配列は[]となりますので、全ての数字がans配列に移動したことになります。
この段階で処理は終了です。
ans[0] = 1と判明。
[[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0]]
ans[1] = 2と判明。
[[1, 2, 0, 3], [1, 2, 3, 0]]
ans[2] = 3と判明。
[1, 2, 3, 0]
これでperm_count関数が完成したので、レシーバー、引数にそれぞれ値を渡し、戻り値の配列をjoin関数で結合してあげれば完成です！！
ありがとうございました！
高速化結果
このように、順列を全て生成せず、n番目に直接アクセスすることで処理速度を高速にしました。
結果は次の通りです。
修正前
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
修正後
ruby problem24.rb 0.12s user 0.11s system 75% cpu 0.305 total
だいぶ早いですね！