나는 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']
답변
이 단일 라이너는 모든 조합 ( 원래 목록 / 세트에 고유 한 요소 가 포함 된 경우 0
및 n
항목 간 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']]
온라인으로 사용해보십시오 :
답변
본인은 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