#プロジェクトオイラー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文1ループ目
・arr配列
の要素を削除していくので[]
の状態になるまでループを継続。
・a = factorial(arr.size - 1)
factorial関数
は引数の「階乗」を求める。
ここで求めているのは先頭の数字を固定した際の、後に続く数字の組み合わせの数。
例)
[0,1,2,3]の4つの数字の順列を求める際、
0から始まる数字は3!通りあります。
1から〜、2から〜、3〜からの場合も同様。
・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
だいぶ早いですね!