15個の数字のリストがあり、それらの数字の32,768の組み合わせすべてを生成するコードを作成する必要があります。
私が探しているものを明らかに実行するコードを（グーグルで）見つけましたが、コードはかなり不透明であり、使用することに慎重です。さらに、もっとエレガントな解決策が必要だと感じています。
私が思い浮かぶのは、1〜32768の10進数をループしてバイナリに変換し、バイナリ表現をフィルターとして使用して適切な数値を選択することだけです。
誰かがより良い方法を知っていますか？使用してmap()、多分？
この回答には、1つの側面がありませんでした。OPは、長さ「r」の組み合わせだけでなく、すべての組み合わせを要求しました。
したがって、すべての長さ「L」をループする必要があります。
import itertools
stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
for subset in itertools.combinations(stuff, L):
print(subset)
または -- おしゃれになりたい場合 (または、あなたのコードを後で読む人の頭を曲げる場合) -- 「combinations()」ジェネレーターのチェーンを生成し、それを繰り返すことができます。
from itertools import chain, combinations
def all_subsets(ss):
return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))
for subset in all_subsets(stuff):
print(subset)
itertools.combinationsを見てください：
itertools.combinations(iterable, r)入力iterableから要素のr長のサブシーケンスを返します。
組み合わせは、辞書式順序で発行されます。したがって、入力反復可能オブジェクトがソートされている場合、組み合わせタプルはソートされた順序で生成されます。
2.6以降、電池が含まれています！
これも itertools を使用した怠惰なワンライナーです。
from itertools import compress, product
def combinations(items):
return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
# alternative: ...in product([0,1], repeat=len(items)) )
この回答の背後にある主なアイデア: 2^N の組み合わせがあります。長さ N のバイナリ文字列の数と同じです。バイナリ文字列ごとに、「1」に対応するすべての要素を選択します。
items=abc * mask=###
|
V
000 ->
001 -> c
010 -> b
011 -> bc
100 -> a
101 -> a c
110 -> ab
111 -> abc
考慮事項:
len(...)これにはonを呼び出すことができる必要がありますitems(回避策:itemsがジェネレーターのような iterable のようなものである場合は、最初に でリストに変換しますitems=list(_itemsArg))itemsランダムでないことが必要です (回避策: 気が狂わないでください)。{2,2,1}でない場合{2,1,1}、両方が折りたたまれ{2,1}ます (回避策:collections.Counterのドロップイン置換として使用しsetます。基本的にはマルチセットです...ただし、ハッシュ可能にする必要がある場合は、後で使用する必要があるtuple(sorted(Counter(...).elements()))場合があります)デモ
>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]
>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]
@Dan H による非常に支持された回答の下のコメントでは、 Dan 自身によるものを含む、ドキュメントpowerset()のレシピについて言及されています。ただし、これまでのところ、誰も回答として投稿していません。問題への最善のアプローチではないにしても、おそらくより良いアプローチの1つであり、別のコメント投稿者から少し励まされたので、以下に示します. この関数は、可能なすべての長さのリスト要素のすべての一意の組み合わせを生成します (ゼロとすべての要素を含むものを含む)。itertools
注: わずかに異なる目標が、一意の要素の組み合わせのみを取得することである場合は、行s = list(iterable)をに変更してs = list(set(iterable))、重複する要素を削除します。とにかく、iterableが最終的にジェネレーターで動作する手段に変わるという事実listは（他のいくつかの回答とは異なります）。
from itertools import chain, combinations
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable) # allows duplicate elements
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
print('combo #{}: {}'.format(i, combo))
出力：
combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)
このワンライナーは、すべての組み合わせ (元のリスト/セットに個別の要素が含まれている場合は と の間) を提供し、ネイティブ メソッドを使用し0ます。nnitertools.combinations
from itertools import combinations
input = ['a', 'b', 'c', 'd']
output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])
from itertools import combinations
input = ['a', 'b', 'c', 'd']
output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], [])
出力は次のようになります。
[[],
['a'],
['b'],
['c'],
['d'],
['a', 'b'],
['a', 'c'],
['a', 'd'],
['b', 'c'],
['b', 'd'],
['c', 'd'],
['a', 'b', 'c'],
['a', 'b', 'd'],
['a', 'c', 'd'],
['b', 'c', 'd'],
['a', 'b', 'c', 'd']]
オンラインで試す:
再帰を使用したものを次に示します。
>>> import copy
>>> def combinations(target,data):
... for i in range(len(data)):
... new_target = copy.copy(target)
... new_data = copy.copy(data)
... new_target.append(data[i])
... new_data = data[i+1:]
... print new_target
... combinations(new_target,
... new_data)
...
...
>>> target = []
>>> data = ['a','b','c','d']
>>>
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']
Ben が実際にすべての組み合わせを要求したという Dan H に同意します。itertools.combinations()すべての組み合わせを与えるわけではありません。
もう 1 つの問題は、入力 iterable が大きい場合、リスト内のすべてのものではなく、ジェネレーターを返す方がおそらく良いということです。
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
itertools やその他の追加ライブラリをインポートせずに答えを求める人のために、この関数を追加すると思いました。
def powerSet(items):
"""
Power set generator: get all possible combinations of a list’s elements
Input:
items is a list
Output:
returns 2**n combination lists one at a time using a generator
Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
"""
N = len(items)
# enumerate the 2**N possible combinations
for i in range(2**N):
combo = []
for j in range(N):
# test bit jth of integer i
if (i >> j) % 2 == 1:
combo.append(items[j])
yield combo
シンプルな利回りジェネレーターの使用法:
for i in powerSet([1,2,3,4]):
print (i, ", ", end="")
上記の使用例からの出力:
[] , [1] , [2] , [1, 2] , [3] , [1, 3] , [2, 3] , [1, 2, 3] , [4] , [1, 4] , [2, 4] , [1, 2, 4] , [3, 4] , [1, 3, 4] , [2, 3, 4] , [1, 2, 3, 4] ,
関数を使用する別の解決策 (ワンライナー) を次に示しitertools.combinationsますが、ここでは (for ループまたは合計とは対照的に) 二重リスト内包表記を使用します。
def combs(x):
return [c for i in range(len(x)+1) for c in combinations(x,i)]
デモ：
>>> combs([1,2,3,4])
[(),
(1,), (2,), (3,), (4,),
(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4),
(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4),
(1, 2, 3, 4)]
3つの機能:
import sys
def permutations(a):
return combinations(a, len(a))
def combinations(a, n):
if n == 1:
for x in a:
yield [x]
else:
for i in range(len(a)):
for x in combinations(a[:i] + a[i+1:], n-1):
yield [a[i]] + x
def combinationsNoOrder(a, n):
if n == 1:
for x in a:
yield [x]
else:
for i in range(len(a)):
for x in combinationsNoOrder(a[:i], n-1):
yield [a[i]] + x
if __name__ == "__main__":
for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])):
print(s)
また、優れたパッケージのpowerset機能も使用できます。more_itertools
from more_itertools import powerset
l = [1,2,3]
list(powerset(l))
# [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
OPの要件を満たしていることも確認できます
from more_itertools import ilen
assert ilen(powerset(range(15))) == 32_768
以下は、他の同様の回答https://stackoverflow.com/a/23743696/711085と同様の「標準的な再帰的回答」です。(N! 個の順列をすべて処理する方法はないため、スタック スペースが不足することを現実的に心配する必要はありません。)
すべての要素を順番に訪問し、それを取るか、そこから離れます (このアルゴリズムから 2^N カーディナリティを直接見ることができます)。
def combs(xs, i=0):
if i==len(xs):
yield ()
return
for c in combs(xs,i+1):
yield c
yield c+(xs[i],)
デモ：
>>> list( combs(range(5)) )
[(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)]
>>> list(sorted( combs(range(5)), key=len))
[(),
(0,), (1,), (2,), (3,), (4,),
(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3),
(2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2),
(3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1),
(4, 3, 2, 1, 0)]
>>> len(set(combs(range(5))))
32
itertools からの組み合わせ
import itertools
col_names = ["aa","bb", "cc", "dd"]
all_combinations = itertools.chain(*[itertools.combinations(col_names,i+1) for i,_ in enumerate(col_names)])
print(list(all_combinations))
これは私の実装です
def get_combinations(list_of_things):
"""gets every combination of things in a list returned as a list of lists
Should be read : add all combinations of a certain size to the end of a list for every possible size in the
the list_of_things.
"""
list_of_combinations = [list(combinations_of_a_certain_size)
for possible_size_of_combinations in range(1, len(list_of_things))
for combinations_of_a_certain_size in itertools.combinations(list_of_things,
possible_size_of_combinations)]
return list_of_combinations
リスト内包表記の使用:
def selfCombine( list2Combine, length ):
listCombined = str( ['list2Combine[i' + str( i ) + ']' for i in range( length )] ).replace( "'", '' ) \
+ 'for i0 in range(len( list2Combine ) )'
if length > 1:
listCombined += str( [' for i' + str( i ) + ' in range( i' + str( i - 1 ) + ', len( list2Combine ) )' for i in range( 1, length )] )\
.replace( "', '", ' ' )\
.replace( "['", '' )\
.replace( "']", '' )
listCombined = '[' + listCombined + ']'
listCombined = eval( listCombined )
return listCombined
list2Combine = ['A', 'B', 'C']
listCombined = selfCombine( list2Combine, 2 )
出力は次のようになります。
['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']
ドキュメントに記載されているように
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9]
for i in combinations(x, 2):
print i