数え上げよう(順列編)
順列を数え上げる場合、n個の置換を生成する関数を作って、組み合わせを生成する関数から呼ぶことにする。手抜きですね。
require "Combination" class Permutation def Permutation.each(ary) case ary.size when 1 yield ary when 2 yield ary yield ary.reverse else for i in 0...ary.size for j in 0...ary.size if i > j a = ary.clone b = a.slice!(i) c = a.slice!(j) Permutation.each(a) do |item| yield [b,c] + item end elsif i < j a = ary.clone c = a.slice!(j) b = a.slice!(i) Permutation.each(a) do |item| yield [b,c] + item end end end end end end def Permutation.eachSeq(n,k) if n < k return end Combination.eachSet(n,k) do |c| Permutation.each(c) do |a| yield a end end end end
n=4 k=2 のときは、 を意味していて、 [0,1] から [3,2] までのように 0 から 3 までの数字から 2 つ取り出す方法を配列に並べて出力します。順序は辞書式ではありません。
Permutation.eachSeq(4,2) do |c| p c end
[0, 1]
[1, 0]
[0, 2]
[2, 0]
[1, 2]
[2, 1]
[0, 3]
[3, 0]
[1, 3]
[3, 1]
[2, 3]
[3, 2]
パフォーマンスは
n = 15 k = 5 count = 0 t = Time.now Permutation.eachSeq(n,k) do |c| count += 1 end p Time.now - t p count
Intel Core2 2.13GHz Linux ruby1.8.6 で
5.735
360360
でした。36万の列挙に5.7秒。手抜きしているので遅いですな。