部分集合を求めるスクリプト

概要

id:shibutaka526 がブログ頑張っているのを見て刺激を受け、布団に入って寝ようとしていたけど無性にスクリプトを書きたくなったので彼の以下のエントリーの問題をPythonで解いてみたという話.

スクリプト

恐縮ながらポイントを挙げると 0~2の要素数乗までの2進数の以下のような文字列を生成して、

"000", "001", "010", "011", "100", "101", "110", "111"

i番目の文字列が入力された配列のi番目の要素の対として、文字列のi番目が0/1のとき、i番目の要素を使わない/使う。
といったような2進数の文字列をスイッチとして使ったところが個人的に工夫出来たと思っている。
このスクリプト書いてみて、2分岐の実装方法として2進数を使って書けるんだな〜っていうのが発見だった.

#!/usr/bin/env python
# coding:utf-8

def solve(input):
    n = len(input)
    pattern ,result = [], ["φ"]

    for i in range(1, pow(2, n)):
        s = "%0" + str(n) + "d"
        pattern.append(s % int(format(i, 'b')))

    for i in pattern:
        s = ""
        for j, v in enumerate(list(i)[::-1]):
            if v == "1" : s += input[j]
        result.append(s)
    return result


if __name__ == "__main__":
    # test
    test = [['a'],
            ['a', 'b'],
            ['a', 'b', 'c'],
            ['a', 'b', 'c', 'd']]
    for input in test:
        print solve(input)
        print '-------------------------'
result
['\xcf\x86', 'a']
-------------------------
['\xcf\x86', 'a', 'b', 'ab']
-------------------------
['\xcf\x86', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
-------------------------
['\xcf\x86', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc', 'd', 'ad', 'bd', 'abd', 'cd', 'acd', 'bcd', 'abcd']
-------------------------

最後に

向上心あふれる人たちが周りにいて幸せだということをここ最近感じている。彼らに負けないように頑張りたい。