Monday, October 13, 2008

組み合わせを作るアルゴリズム#2

先日のエントリで集合の部分集合の表示にはbinary countingがあざやかにキマル、という話を書きました。これはすべての部分集合の表示でした。すべての部分集合は必要なく、エントリ数がk個のものだけで良い場合はどうすればよいでしょうか。

例えば{0,1,...,4}の集合の部分集合から要素数が3個のものだけを表示したい場合です。{0,1,2}, {0,1,3},...というのを表示したいとする場合。

この関係を使えば簡単とのことです。n個からk個を選ぶ組み合わせの記号を(n, k)と書くことにすると

(n, k) = (n-1, k) + (n-1, k-1)

右辺は、今の1個をパスして次以降でk取る組み合わせと、今の1個をとって後k-1個選ぶ組み合わせの和です。

これをプログラムで書くと以下のようになります。n,kは上のものと同じ、iは今の場所です。
def ksubset(n, k, i, ans):
if k == 0:
print ans
return
if n == 0:
return
ksubset(n-1, k-1, i+1, ans+[i])
ksubset(n-1, k, i+1, ans)

ksubset(5, 3, 0, [])として実行した結果が以下です。
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

お気づきの通り、このkの考慮をやめれば、部分集合全体となります。以下のように書き直しましょう。
def allsubset(n, i, ans):
if n == 0:
print ans
return
allsubset(n-1, i+1, ans+[i])
allsubset(n-1, i+1, ans)

allsubset(5, 0, [])として実行したのが以下です。長いので中略しました。
[0, 1, 2, 3, 4]
[0, 1, 2, 3]
[0, 1, 2, 4]
[0, 1, 2]
;
;
[3, 4]
[3]
[4]
[]

これでもそんなに難しくはないですね。

No comments: