bit全探索

リストの要素の選び方をビット全探索で列挙する

def all_pattern(list):
    """リストの要素の取り出し方

    ビット全探索でリストから要素の取り出し方を全て列挙する

    NOTE: O(n) = n*2**n

    Args:
        list (list): 使える要素
    """
    n = len(list)
    for i in range(2 ** n):
        foo = []
        for j in range(n):
            if ((i >> j) & 1):   # 二進数iのj桁目が1ならlistのj番目の要素を追加する
                foo.append(list[j])
        yield foo

この関数にリストを渡すと全組み合わせがイテレーターになって帰ってきます。
使い方は下記のような感じです。
itertoolsに同じことができるのないのかなぁ

fruits = ['apple', 'melon', 'banana', 'orange']
for p in all_pattern(fruits):
    print(p)
# >>
[]
['apple']
['melon']
['apple', 'melon']
['banana']
['apple', 'banana']
['apple', 'melon', 'banana']