最近プログラムを作っている際に全列挙の問題に直面しました
(このブログでは主にPyhtonを使っていきます、宣言し忘れてたので、、、笑)

全列挙とは？

Input: 1,2,3,4  
Output: None,1,2,3,4,12,13,14,23,24,
              34,123,124,134,234,1234

のように入力の要素全てを舐めるように見て組み合わせを出力するという作業です。これをプログラム中で出力したいと考えた時にどのようにしたら良いでしょうか？

データが木構造を持っている場合

木構造とは下の図のようなやつです()
親が子を持つようなデータ構造ですね、はい
f:id:wasabin_idol:20171226003513p:plain
こういう場合は再帰を使って

def f():
    hoge...
    if ~
        f()
    else
    return ~~

のようにしてデータが一番下まで降りたら上に戻ってくるような再帰関数を書けば終わります。

データがリストだった場合は？

ここからが本題です、僕が悩んだ問題は以下のような問題です。

Input: list a = [1,2,3,4] 
Output: Answer = [[None],[1],[2],[3],[4],[12],[13],[14],[23],[24],
              [34],[123],[124],[134],[234],[1234]]

上のようにリストから全列挙したリストを返してほしい場合どうしたら良いでしょうか。。。。？
再帰関数を使ってでも書けそうなのですがここで一つ便利なパッケージであるitertoolsを紹介します。

itertoolsとは？

Pyhonの標準ライブラリです

10.1. itertools — 効率的なループ実行のためのイテレータ生成関数 — Python 3.6.3 ドキュメント

このライブラリではイテレーションを組む際に必要な作業を担ってくれる便利な物になっています笑。 itertoolsを使うことで順列・組み合わせ・直積を容易に生成してくれます。また順列・組み合わせ・直積などから上の全列挙・重複順列・重複組み合わせなども生成できます。

>>> a = [1,2,3]
>>> list(itertools.permutations(a))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
>>> a = [1,2,3,4,5,6,7,8,9]
>>> list(itertools.combinations(a,2))
[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 6), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9), (7, 8), (7, 9), (8, 9)]
>>> len(list(itertools.combinations(a,2)))
36

上を見るとpermutationsで順列が、combinationsでリストと何個取るのかを引数にしてそれに対応した組み合わせが確かに出力されています。
今回の全列挙は以下のようにすると即出力されます。

>>> a = [1,2,3]
>>> for i in range(len(a)+1):
...     for j in itertools.combinations(a,i):
...             print(j)
...
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)