数え上げよう(組合せ編)
順列・組み合わせは高校数学でも出てくるし、パズル的な問題でも応用範囲が広いのだから、もっとプログラミングのネタとしても取り上げられてもいいと思うんだけどな。配列と if と for がわかればできるし。
というわけでこの手の個数を数えるものについて、列挙関数の実装をしてみる。自分用のメモなのであまりアルゴリズム的には工夫していないです。もっと速い実装を見つけたらそれも紹介するというスタンスで。実装は ruby の each 系のメソッドとして使えるようにします。
まずは組合せ Combination から。
class Combination def Combination.eachSet(n,k) c = Array.new(k){ |i| i } while true yield c d0 = c.first if d0 == n-k break end d1 = d0 i1 = 0 c.each_with_index{ |d,i| if d == d0+i d1 = d i1 = i else break end } if d1 == d0 c.insert( i1+1, c[i1]+1 ) c.shift else c[i1] += 1 i1.times{ |i| c[i] = i } end end end end
n=5 k=2 のときは、 を意味していて、 [0,1] から [3,4] までのように 0 から 4 までの数字から 2 つを選んで小さい方から配列に並べて出力します。
Combination.eachSet(5,2) do |c| p c end
[0, 1]
[0, 2]
[1, 2]
[0, 3]
[1, 3]
[2, 3]
[0, 4]
[1, 4]
[2, 4]
[3, 4]
パフォーマンスは
n = 20 k = 10 count = 0 t = Time.now Combination.eachSet(n,k) do |c| count += 1 end p Time.now - t p count
Intel Core2 2.13GHz Linux ruby1.8.6 で
2.427908
184756
でした。18万の列挙に2.4秒。もうちょっと速くしたいなあ。