Sunday, January 04, 2009

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

以前、k-subsetのことを書きました。Pythonで書きましたがC言語に直訳できそうな書き方でした。私のPythonの書き方はいつもそれで、たぶんPythonらしくないのでしょう。ダサイ書き方なんですよね。昨日某所にて同じことを以下のように書いているのをみてそう感じました。


def ksubset2(n, k, pos):
if k > 0:
for i in xrange(pos, n - k + 1):
for s in ksubset2(n, k - 1, i + 1):
yield [i] + s
else:
yield []


すごいなあ。格好いい。私がやってもこういう風には絶対ならないですね。これはジェネレータなのでksubset2(5,3,0)に前と同じ組み合わせが入っていることになります。

しかし、自分でやるとしたら、やっぱりCに置き換えやすい書き方をしておきますかね。Pythonで遅ければCに直すという理由で。つまりジェネレータは使わないのです。

ちなみに、某所でみたのは上のようにnで上限を渡すのではなくて、同じことではありますが以下のようにseqに元の集合を入れて渡すものでした。

def ksubset3(seq, k):
if k > 0:
for i in xrange(0, len(seq) - k + 1):
for s in ksubset3(seq[i+1:], k - 1):
yield [seq[i]] + s
else:
yield []

No comments: