[python] 목록 요소의 가능한 모든 조합을 얻는 방법은 무엇입니까?

나는 15 개의 숫자가있는 목록을 가지고 있으며 그 숫자의 32,768 조합을 모두 생성하는 코드를 작성해야합니다.

코드를 찾았 습니다 찾고있는 것을 분명히하는 (구글링에 의해)를 찾았지만 코드가 상당히 불투명하고 사용하는 것에주의를 기울였습니다. 또한 더 우아한 솔루션이 있어야한다고 생각합니다.

나에게 발생하는 유일한 일은 십진 정수 1-32768을 반복하여 이진수로 변환하고 이진 표현을 필터로 사용하여 적절한 숫자를 선택하는 것입니다.

누구든지 더 나은 방법을 알고 있습니까? 사용 map(), 아마?



답변

itertools.combinations를 살펴보십시오 .

itertools.combinations(iterable, r)

입력 iterable에서 요소의 r 길이 하위 시퀀스를 반환합니다.

조합은 사전 식 정렬 순서로 방출됩니다. 따라서 입력 반복 가능 항목이 정렬되면 조합 튜플이 정렬 된 순서로 생성됩니다.

2.6부터 배터리가 포함되어 있습니다!


답변

이 답변 은 한 가지 측면을 놓쳤습니다. 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를 사용하는 게으른 원 라이너가 있습니다.

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)) )

이 답변의 기본 개념은 길이가 N 인 이진 문자열의 수와 동일한 2 ^ N 조합입니다. 각 이진 문자열에 대해 “1”에 해당하는 모든 요소를 ​​선택합니다.

items=abc * mask=###
 |
 V
000 ->
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

고려해야 할 사항 :

  • 이것은 당신이 호출 할 수 있어야 len(...)items있는 경우 : 해결 방법 ( items발전기와 같은 반복 가능한 같은 것입니다, 먼저 목록으로 바꿀items=list(_itemsArg) )
  • 이를 위해서는 반복 순서가 items 가 무작위가 아니어야합니다 (해결 방법 : 제정신이 아닙니다).
  • 이 항목은 고유의, 또는 다른 것을 요구 {2,2,1}하고 {2,1,1}에 모두 붕괴 할 것이다 {2,1}(: 사용 해결 collections.Counter드롭 인 교체 등을 set, 나중에 사용해야 할 수도 있지만이 … 기본적으로 MULTISET의 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()레시피에 대한 언급이 있습니다. 그러나 지금까지 아무도 답변으로 게시하지 않았습니다. 문제에 대한 최선의 접근 방법은 아니지만 더 나은 방법 중 하나 일 수 있으며 다른 의견 자가 약간의 격려 를 받으면 아래에 나와 있습니다. 이 함수는 가능한 모든 길이 의 목록 요소 (0 및 모든 요소를 ​​포함하는 요소 포함)의 고유 한 모든 조합을 생성 합니다 .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)


답변

다음은 재귀를 사용하는 것입니다.

>>> 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']


답변

이 단일 라이너는 모든 조합 ( 원래 목록 / 세트에 고유 한 요소 가 포함 된 경우 0n항목 간 n)을 제공하고 기본 메소드를 사용합니다.itertools.combinations .

파이썬 2

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])

파이썬 3

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']]

온라인으로 사용해보십시오 :

http://ideone.com/COghfX


답변

본인은 Ben이 실제로 모든 조합을 요청한 Dan H에 동의합니다 . itertools.combinations()모든 조합을 제공하지는 않습니다.

또 다른 문제는 입력 iterable이 큰 경우 목록의 모든 것 대신 생성기를 반환하는 것이 좋습니다.

iterable = range(10)
for s in xrange(len(iterable)+1):
  for comb in itertools.combinations(iterable, s):
    yield comb