tkenichi の日記

毒舌皮肉系恥さらし日記

数え上げよう(組合せ編)

順列・組み合わせは高校数学でも出てくるし、パズル的な問題でも応用範囲が広いのだから、もっとプログラミングのネタとしても取り上げられてもいいと思うんだけどな。配列と 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 のときは、$_5C_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秒。もうちょっと速くしたいなあ。