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]
[]

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

pythonメモ 16進数

pythonで16進数を表示しようというとき、私は馬鹿の1つ覚えで以下のようにやっていました。
>>> a = 43
>>> print "%x" % a
2b
>>> print "%X" % a
2B

ところが、このような手頃な関数があるのでした。
>>> hex(a)
'0x2b'

さらに大文字で表示したいという場合には以下のような手段があるのでした。
>>> hex(a).upper()
'0X2B'

Xまで大文字となるのはご愛嬌ですね。

Tuesday, October 07, 2008

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

ちょっと家にいなければならない用があったので、例のごとくProject eulerであそんでいました。
いましがた気持ちよく一問解けたので今日はもうおしまい。

ところで集合の部分集合をすべてリストアップするにはどうすればよいでしょうか。
つまり要素がN個の集合{1,2,3,4,...,N}があるとして、この集合から要素数1からN個までの部分集合を全部書き出すのです。{1},...,{N},{1,2},{2,3},....,{N-1,N},{1,2,3},...,,,,...{1,....,N}てのを全部です。どうやるのがよいでしょうか。順列だの組み合わせだのってのは概念は簡単なのですが、あんがい面倒なものが多いですね。


今日やった問題、最初勘違いしていて、部分集合を作る問題かと思って、これを実装してしまってました。結局これは使わなかったのですが。いざやろうとすると迷いますね。

先日買った本(赤い方の本)で調べたのです。「辞書順」は意外に大変だよ、と書いてある、そうそう、それやったことある。大変だった。簡単な方法はbinary countingだよと書いてありました。部分集合の数は2^N個あるので、1から2^N-1までの数を生成する。その数を2進数で表して1の立った場所を{1,...,N}の位置から選んで部分集合の要素とするというもの。なかなかシンプルでよろしいですね。これなら実装も簡単です。