破棄されたブログ

このブログは破棄されました。

直積を実装する

Python には、 itertools パッケージに product() があるわけですが、 今回はこれを自分で実装してみます。

2 変数の直積

2 変数の直積については、特に難しく考えず、愚直に実装します。

def product(xs, ys):
    return (x + y for x in xs for y in ys)

assert list(product('ab', 'cd')) == ['ac', 'ad', 'bc', 'bd']

3 変数以上の直積

3 変数以上の直積になると、よくわからなくなるので定義を確認します。

Wikipedia によると、 直積集合は結合法則が成り立つと 見なして よいとされています。

結合法則が成り立つということは、元となる集合を 2 つずつ再帰的に関数を適用することで 3 変数以上の直積を取り出すことができるはずです。

2 変数版の関数を用いて試してみます。

assert list(product(product('ab', 'cd'), 'ef')) == ['ace', 'acf', 'ade', 'adf', 'bce', 'bcf', 'bde', 'bdf']

したがって、3 変数以上の直積集合を得るための関数は、次の通り実装できます。

def product(*args):
    xs, ys, args = args[0], args[1], args[2:]
    if len(args) > 0:
        return (z for z in product(product(xs, ys), *args))
    else:
        return (x + y for x in xs for y in ys)

ただ、この実装は少々冗長です。 product(product(product(... と関数を適用していくわけですから、これは畳みこみを使えばよいはずです。

実際に試してみます。

from functools import reduce

def product(xs, ys):
    return (x + y for x in xs for y in ys)

assert list(reduce(product, ['ab', 'cd', 'ef'])) == ['ace', 'acf', 'ade', 'adf', 'bce', 'bcf', 'bde', 'bdf']

reduce() を使っても期待通りの結果を得ることできました。

from functools import reduce

 def product(*args):
     return reduce(
         lambda xs, ys: (x + y for x in xs for y in ys),
         args
     )

assert list(reduce(product, ['ab', 'cd', 'ef'])) == ['ace', 'acf', 'ade', 'adf', 'bce', 'bcf', 'bde', 'bdf']

というわけで、 reduce() を使うと非常にシンプルな実装で直積を実装することがわかりました。

最近の悩みは、もっぱら、この手のあんまり生産性にもお金にも寄与しないことばっか楽しくなって、石油王への道が遠のいていることです。

広告を非表示にする