部分集合を求めるスクリプト
概要
id:shibutaka526 がブログ頑張っているのを見て刺激を受け、布団に入って寝ようとしていたけど無性にスクリプトを書きたくなったので彼の以下のエントリーの問題をPythonで解いてみたという話.
- 部分集合を求めるプログラム - shibu_t最強伝説
- ※ こちらの問題の解釈が間違っていて、違う問題を解いているかもしれません。
スクリプト
恐縮ながらポイントを挙げると 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'] -------------------------
最後に
向上心あふれる人たちが周りにいて幸せだということをここ最近感じている。彼らに負けないように頑張りたい。