임의의 길이의 목록 요소의 가능한 모든 (2^N) 조합 가져오기
저는 15개의 숫자가 있는 목록을 가지고 있습니다.어떻게 32,768개의 숫자 조합(즉, 임의의 수의 원소를 원래 순서대로)을 모두 생성할 수 있습니까?
저는 소수점 정수 1~32768을 반복해서 각 숫자의 이진수 표현을 필터로 사용하여 적절한 목록 요소를 선택하는 것을 생각했습니다.더 좋은 방법이 있을까요?
특정 길이의 조합은 길이 n의 모든 (n-choose-k) 조합을 참조하십시오. 해당되는 경우 해당 질문을 사용하여 중복 항목을 닫으십시오.
조합론에 대한 질문을 중복으로 닫을 때 문제를 설명하는 데 사용된 단어가 아니라 OP가 실제로 무엇을 원하는지 확인하는 것이 매우 중요합니다.예를 들어 데카르트 제품(여러 목록의 데카르트 제품을 가져오는 방법 참조)을 원하는 사람들이 "조합"에 대해 묻는 것은 매우 일반적입니다.
이 대답은 한 가지 측면을 놓쳤습니다. OP가 모든 조합을 요청했습니다.길이 "r"의 조합만이 아닙니다.
따라서 모든 길이 "L"을 반복해야 합니다.
import itertools
stuff = [1, 2, 3]
for L in range(len(stuff) + 1):
for subset in itertools.combinations(stuff, L):
print(subset)
또는 -- 만약 당신이 선명해지고 싶다면(또는 당신의 코드를 읽는 사람의 뇌를 구부리고 싶다면), 당신은 "조합()" 생성기 체인을 생성하고, 그것을 통해 반복할 수 있습니다.
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)
iter tools.combinations를 확인합니다.
itertools.combinations(iterable, r)
입력 가능한 요소의 반환기 길이 연속입니다.
조합은 사전순으로 정렬됩니다.따라서 입력 가능한 항목이 정렬되면 조합 튜플이 정렬된 순서로 생성됩니다.
2.6부터 배터리가 포함되어 있습니다!
@Dan H에 의해 매우 지지를 받은 답변 아래 댓글에, 언급은 다음과 같습니다.powerset()
Dan이 직접 작성한 요리법을 포함하여 설명서에 나와 있습니다.하지만, 지금까지 아무도 그것을 답으로 게시하지 않았습니다.문제에 대한 최선의 접근법은 아닐지라도 더 나은 방법 중 하나일 수 있으므로 다른 의견제출자의 약간의 격려를 받아 아래에 나와 있습니다.함수는 가능한 모든 길이의 리스트 요소(0과 모든 요소 포함)의 모든 고유한 조합을 생성합니다.
참고: 미묘하게 다른 목표가 고유한 요소의 조합만 얻는 것이라면 라인을 변경합니다.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)
다음은 게으른 원라이너로, 또한 iter 도구를 사용합니다.
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
방법: if (문제: 방경우법해결)▁(해items
으로, 제레이터반가것입으로 으로 전환합니다. 먼저 목록으로 전환합니다.items=list(_itemsArg)
) - 는 이위해반순서가에 대한 합니다.
items
무작위가 아닙니다(해결 방법: 제정신이 아닙니다). - . 않으면 항목이 고유해야 합니다. 그렇지 않으면
{2,2,1}
그리고.{2,1,1}
둘 다 붕괴될 것입니다.{2,1}
방법: use (사용법: 사용결방)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'}]
이것은 재귀를 지원하는 모든 프로그래밍 언어로 쉽게 이전할 수 있는 접근 방식입니다(어떤 도구도, 어떤 산출물도, 어떤 목록 이해도).
def combs(a):
if len(a) == 0:
return [[]]
cs = []
for c in combs(a[1:]):
cs += [c, c+[a[0]]]
return cs
>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]
재귀를 사용하는 방법은 다음과 같습니다.
>>> 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
고유한 요소) 및 네이티브 방법을 사용합니다.
파이썬 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']]
온라인으로 사용해 보십시오.
다음과 같은 간단한 코드를 사용하여 Python에서 목록의 모든 조합을 생성할 수 있습니다.
import itertools
a = [1,2,3,4]
for i in xrange(0,len(a)+1):
print list(itertools.combinations(a,i))
결과:
[()]
[(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)]
저는 이 기능을 아이터 도구나 다른 추가 라이브러리를 가져오지 않고도 답을 찾는 사람들을 위해 추가할 것이라고 생각했습니다.
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] ,
저는 벤이 정말로 모든 조합을 요청했다는 댄 H의 말에 동의합니다. itertools.combinations()
모든 조합을 제공하지는 않습니다.
또 다른 문제는 입력 가능한 값이 클 경우 목록의 모든 항목 대신 제너레이터를 반환하는 것이 더 낫다는 것입니다.
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
3가지 기능:
- n개 요소 리스트의 모든 조합
- 순서가 구별되지 않는 n개 요소 리스트의 모든 조합
- 모든 순열
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)
from itertools import combinations
features = ['A', 'B', 'C']
tmp = []
for i in range(len(features)):
oc = combinations(features, i + 1)
for c in oc:
tmp.append(list(c))
산출량
[
['A'],
['B'],
['C'],
['A', 'B'],
['A', 'C'],
['B', 'C'],
['A', 'B', 'C']
]
여기에 다음과 같은 또 다른 솔루션(단일 라이너)이 있습니다.itertools.combinations
함수, 하지만 여기서 우리는 이중 목록 이해를 사용합니다(루프 또는 합계에 대한 a와는 반대).
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)]
우수 패키지의 파워셋 기능도 사용할 수 있습니다.
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
모든 조합을 얻기 위해 iter 도구를 사용하는 것이 훨씬 더 실용적이라는 것을 알지만, 당신이 많은 코딩을 원한다면, 당신은 부분적으로 리스트 이해만으로 이것을 달성할 수 있습니다.
두 쌍의 조합의 경우:
lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]
세 쌍의 조합은 다음과 같이 간단합니다.
lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]]
결과는 itertools.combinations를 사용하는 것과 동일합니다.
import itertools
combs_3 = lambda l: [
(a, b, c) for i, a in enumerate(l)
for ii, b in enumerate(l[i+1:])
for c in l[i+ii+2:]
]
data = ((1, 2), 5, "a", None)
print("A:", list(itertools.combinations(data, 3)))
print("B:", combs_3(data))
# A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
# B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
저는 이 문제를 실행하는 방법이 너무 많아서 좋습니다.저는 미래를 위한 참조 답변을 만들기로 결정했습니다.
프로덕션에서 사용할 항목은 무엇입니까?
인터툴의 문서에는 자체적으로 포함된 예제가 있는데, 코드에 사용하는 것이 어떻습니까?일부 사람들은 사용을 제안했습니다.more_itertools.powerset
하지만 그것은 정확히 같은 구현을 가지고 있습니다!내가 당신이라면 작은 것 하나 때문에 패키지 전체를 설치하지 않을 것입니다.아마도 이것이 최선의 방법일 것입니다.
import itertools
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return itertools.chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
기타 가능한 접근법
접근법 0: 조합 사용
import itertools
def subsets(nums):
result = []
for i in range(len(nums) + 1):
result += itertools.combinations(nums, i)
return result
접근법 1: 간단한 재귀
def subsets(nums):
result = []
def powerset(alist, index, curr):
if index == len(alist):
result.append(curr)
return
powerset(alist, index + 1, curr + [alist[index]])
powerset(alist, index + 1, curr)
powerset(nums, 0, [])
return result
접근 2: 역추적
def subsets(nums):
result = []
def backtrack(index, curr, k):
if len(curr) == k:
result.append(list(curr))
return
for i in range(index, len(nums)):
curr.append(nums[i])
backtrack(i + 1, curr, k)
curr.pop()
for k in range(len(nums) + 1):
backtrack(0, [], k)
return result
또는
def subsets(nums):
result = []
def dfs(nums, index, path, result):
result.append(path)
for i in range(index, len(nums)):
dfs(nums, i + 1, path + [nums[i]], result)
dfs(nums, 0, [], result)
return result
접근법 3: 비트 마스킹
def subsets(nums):
res = []
n = len(nums)
for i in range(1 << n):
aset = []
for j in range(n):
value = (1 << j) & i # value = (i >> j) & 1
if value:
aset.append(nums[j])
res.append(aset)
return res
또는 (비트 마스킹이 아니라 정확히 2^n개의 하위 집합이 있다는 직관을 사용함)
def subsets(nums):
subsets = []
expected_subsets = 2 ** len(nums)
def generate_subset(subset, nums):
if len(subsets) >= expected_subsets:
return
if len(subsets) < expected_subsets:
subsets.append(subset)
for i in range(len(nums)):
generate_subset(subset + [nums[i]], nums[i + 1:])
generate_subset([], nums)
return subsets
접근법 4: 계단식 구조
def subsets(nums):
result = [[]]
for i in range(len(nums)):
for j in range(len(result)):
subset = list(result[j])
subset.append(nums[i])
result.append(subset)
return result
이건 어때요?목록 대신 문자열을 사용했지만, 같은 것입니다.문자열은 Python에서 목록처럼 처리할 수 있습니다.
def comb(s, res):
if not s: return
res.add(s)
for i in range(0, len(s)):
t = s[0:i] + s[i + 1:]
comb(t, res)
res = set()
comb('game', res)
print(res)
없이. itertools
Python 3에서는 다음과 같은 작업을 수행할 수 있습니다.
def combinations(arr, carry):
for i in range(len(arr)):
yield carry + arr[i]
yield from combinations(arr[i + 1:], carry + arr[i])
처음에는carry = "".
다음은 의 두 가지 구현입니다.itertools.combinations
목록을 반환하는 사람
def combinations(lst, depth, start=0, items=[]):
if depth <= 0:
return [items]
out = []
for i in range(start, len(lst)):
out += combinations(lst, depth - 1, i + 1, items + [lst[i]])
return out
하나는 발전기를 반환합니다.
def combinations(lst, depth, start=0, prepend=[]):
if depth <= 0:
yield prepend
else:
for i in range(start, len(lst)):
for c in combinations(lst, depth - 1, i + 1, prepend + [lst[i]]):
yield c
추가 인수는 정적이며 모든 통화에 따라 변경되지 않으므로 도우미 기능을 제공하는 것이 좋습니다.
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
# get a hold of prepend
prepend = [c for c in combinations([], -1)][0]
prepend.append(None)
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]]
이것은 매우 피상적인 사건이지만 미안하기보다는 안전한 것이 좋습니다.
iter 툴의 조합
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))
제가 이 주제에 대해 조금 늦었지만, 제가 누군가를 도울 수 있다고 생각합니다.
사용할 수 있습니다.product
itertools
:
from itertools import product
n = [1, 2, 3]
result = product(n, repeat=3) # You can change the repeat more then n length
print(list(result))
출력:
[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 1),
(1, 3, 2), (1, 3, 3), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 1), (2, 2, 2),
(2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), (3, 1, 2), (3, 1, 3),
(3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3)]
다른 예이지만 반복 인수를 변경합니다.
from itertools import product
n = [1, 2, 3]
result = product(n, repeat=4) # Changing repeat to 4
print(list(result))
출력:
(1, 1, 2, 3), (1, 1, 3, 1), (1, 1, 3, 2), (1, 1, 3, 3), (1, 2, 1, 1),
(1, 2, 1, 2), (1, 2, 1, 3), (1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 3),
(1, 2, 3, 1), (1, 2, 3, 2), (1, 2, 3, 3), (1, 3, 1, 1), (1, 3, 1, 2),
(1, 3, 1, 3), (1, 3, 2, 1), (1, 3, 2, 2), (1, 3, 2, 3), (1, 3, 3, 1),
(1, 3, 3, 2), (1, 3, 3, 3), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 1, 3),
(2, 1, 2, 1), (2, 1, 2, 2), (2, 1, 2, 3), (2, 1, 3, 1), (2, 1, 3, 2),
(2, 1, 3, 3), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 1, 3), (2, 2, 2, 1),
(2, 2, 2, 2), (2, 2, 2, 3), (2, 2, 3, 1), (2, 2, 3, 2), (2, 2, 3, 3),
(2, 3, 1, 1), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 1), (2, 3, 2, 2),
(2, 3, 2, 3), (2, 3, 3, 1), (2, 3, 3, 2), (2, 3, 3, 3), (3, 1, 1, 1),
(3, 1, 1, 2), (3, 1, 1, 3), (3, 1, 2, 1), (3, 1, 2, 2), (3, 1, 2, 3),
(3, 1, 3, 1), (3, 1, 3, 2), (3, 1, 3, 3), (3, 2, 1, 1), (3, 2, 1, 2),
(3, 2, 1, 3), (3, 2, 2, 1), (3, 2, 2, 2), (3, 2, 2, 3), (3, 2, 3, 1),
(3, 2, 3, 2), (3, 2, 3, 3), (3, 3, 1, 1), (3, 3, 1, 2), (3, 3, 1, 3),
(3, 3, 2, 1), (3, 3, 2, 2), (3, 3, 2, 3), (3, 3, 3, 1), (3, 3, 3, 2),
(3, 3, 3, 3)]```
이 코드는 중첩된 목록이 있는 간단한 알고리즘을 사용합니다...
# FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists...
#
# [ [ [] ] ]
# [ [ [] ], [ [A] ] ]
# [ [ [] ], [ [A],[B] ], [ [A,B] ] ]
# [ [ [] ], [ [A],[B],[C] ], [ [A,B],[A,C],[B,C] ], [ [A,B,C] ] ]
# [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ]
#
# There is a set of lists for each number of items that will occur in a combo (including an empty set).
# For each additional item, begin at the back of the list by adding an empty list, then taking the set of
# lists in the previous column (e.g., in the last list, for sets of 3 items you take the existing set of
# 3-item lists and append to it additional lists created by appending the item (4) to the lists in the
# next smallest item count set. In this case, for the three sets of 2-items in the previous list. Repeat
# for each set of lists back to the initial list containing just the empty list.
#
def getCombos(listIn = ['A','B','C','D','E','F'] ):
listCombos = [ [ [] ] ] # list of lists of combos, seeded with a list containing only the empty list
listSimple = [] # list to contain the final returned list of items (e.g., characters)
for item in listIn:
listCombos.append([]) # append an emtpy list to the end for each new item added
for index in xrange(len(listCombos)-1, 0, -1): # set the index range to work through the list
for listPrev in listCombos[index-1]: # retrieve the lists from the previous column
listCur = listPrev[:] # create a new temporary list object to update
listCur.append(item) # add the item to the previous list to make it current
listCombos[index].append(listCur) # list length and append it to the current list
itemCombo = '' # Create a str to concatenate list items into a str
for item in listCur: # concatenate the members of the lists to create
itemCombo += item # create a string of items
listSimple.append(itemCombo) # add to the final output list
return [listSimple, listCombos]
# END getCombos()
Iter 도구를 사용하지 않는 경우:
def combine(inp):
return combine_helper(inp, [], [])
def combine_helper(inp, temp, ans):
for i in range(len(inp)):
current = inp[i]
remaining = inp[i + 1:]
temp.append(current)
ans.append(tuple(temp))
combine_helper(remaining, temp, ans)
temp.pop()
return ans
print(combine(['a', 'b', 'c', 'd']))
이것은 나의 구현입니다.
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 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
목록 이해력 사용:
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']
만약 누군가가 나처럼 거꾸로 된 목록을 찾고 있다면,
stuff = [1, 2, 3, 4]
def reverse(bla, y):
for subset in itertools.combinations(bla, len(bla)-y):
print list(subset)
if y != len(bla):
y += 1
reverse(bla, y)
reverse(stuff, 1)
flag = 0
requiredCals =12
from itertools import chain, combinations
def powerset(iterable):
s = list(iterable) # allows duplicate elements
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
stuff = [2,9,5,1,6]
for i, combo in enumerate(powerset(stuff), 1):
if(len(combo)>0):
#print(combo , sum(combo))
if(sum(combo)== requiredCals):
flag = 1
break
if(flag==1):
print('True')
else:
print('else')
파티에 늦었지만 제가 찾은 해결책을 같은 문제에 대해 공유하고 싶습니다.구체적으로, 저는 순차적인 조합을 하려고 했기 때문에 "STAR"에 대해서는 "STAR", "TA", "AR"을 원했지만 "SR"은 원하지 않았습니다.
lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
for i in lst:
lstCombos.append(lst[lst.index(i):lst.index(i)+Length])
중복 항목은 마지막 줄 앞에 있는 경우 추가로 필터링할 수 있습니다.
lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
for i in lst:
if not lst[lst.index(i):lst.index(i)+Length]) in lstCombos:
lstCombos.append(lst[lst.index(i):lst.index(i)+Length])
어떤 이유로 인해 출력에 빈 목록이 반환되면 다음과 같이 추가했습니다.
for subList in lstCombos:
if subList = '':
lstCombos.remove(subList)
언급URL : https://stackoverflow.com/questions/464864/get-all-possible-2n-combinations-of-a-list-s-elements-of-any-length
'programing' 카테고리의 다른 글
손상된 파일 처리 (0) | 2023.05.17 |
---|---|
Azure 큐 저장소에서 개체 메시지 전달 (0) | 2023.05.17 |
상위 양식의 중앙 MessageBox (0) | 2023.05.17 |
.NET에 문자열이나 문자를 반복하는 기능이 내장되어 있습니까? (0) | 2023.05.17 |
노드 버전 관리자 설치 - nvm 명령을 찾을 수 없습니다. (0) | 2023.05.17 |