如何获得列表元素的所有可能的组合？
我有一个包含15个数字的列表，我需要编写一些代码来生成这些数字的所有32,768个组合。
我发现了一些代码 （通过谷歌search），显然做我在找什么，但我发现代码相当不透明，并谨慎使用它。 另外我有一种感觉，必须有一个更优雅的解决scheme。
唯一发生在我身上的将是循环通过十进制整数1-32768并将其转换为二进制，并使用二进制表示作为筛选器来挑选出适当的数字。
有谁知道更好的方法？ 使用map() ，也许？
看看itertools.combinations ：
itertools.combinations(iterable, r)从input迭代中返回元素的r长度子序列。
组合按字典顺序排列。 所以，如果input迭代被sorting，组合元组将按sorting顺序生成。
从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)
或者 – 如果你想得到时髦（或者弯曲你的代码读取你的代码的人的大脑） – 你可以生成一个“组合（）”生成器的链，并遍历：
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：
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的二进制string的数量相同。对于每个二进制string，select对应于“1”的所有元素。
items=abc * mask=### | V 000 -> 001 -> c 010 -> b 011 -> bc 100 -> a 101 -> ac 110 -> ab 111 -> abc
需要考虑的事项：
- 这就要求你可以在
items上调用len(...)（解决方法：如果items像一个生成器那样可迭代，那么首先将它变成一个列表，其中items=list(_itemsArg)） - 这就要求
items迭代的顺序不是随机的（解决方法：不要疯狂） - 这要求项目是唯一的，否则
{2,2,1}和{2,1,1}都将折叠为{2,1}（解决方法：使用collections.Counter作为collections.Counter的插入replace;它基本上是一个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'}]
这是使用recursion的一个：
>>> 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']
我同意丹H，本的确要求所有的组合。 itertools.combinations()不提供所有组合。
另一个问题是，如果input迭代很大，那么最好是返回一个生成器而不是列表中的所有内容：
iterable = range(10) for s in xrange(len(iterable)+1): for comb in itertools.combinations(iterable, s): yield comb
这一行代码为您提供了所有组合（如果原始列表/集合包含n不同的元素，则为0到n项目之间），并使用本地方法itertools.combinations ：
from itertools import combinations input = ['a', 'b', 'c', 'd'] output = sum([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']]
在线试用：
在@Dan H高度赞成的回答下，在itertools文档中提到powerset()方法 – 包括Dan自己的方法 。 但是 ，到目前为止还没有人发布这个答案。 因为如果不是解决问题的最佳途径，这可能是更好的select之一，并且得到另一位评论者的一点鼓励 ，如下所示。 该函数产生每个可能长度的列表元素的所有唯一组合。
注意 ：如果这个细微差别的目标是只获得唯一元素的组合，那么将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)
你可以使用这个简单的代码在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)]
这里还有另一个解决scheme（ itertools.combinations ），涉及使用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)]
下面是一个“标准的recursion答案”，类似于其他类似的答案https://stackoverflow.com/a/23743696/711085 。 （我们现实中不必担心堆栈空间不足，因为我们无法处理所有的N！排列。）
它依次访问每个元素，并将其放在一边或离开它（我们可以直接看到这个algorithm的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或任何其他额外的库添加此function。
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]，
使用列表理解：
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 = 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
此代码采用嵌套列表的简单algorithm…
# 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 (eg, 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 (eg, 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()
这是我的实现
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
我知道使用itertools来获得所有的组合是非常实用的，但是如果你碰巧想要的话，你可以通过列表理解来实现这一点，如果你想要编码的话
对于两对的组合：
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)]
不使用itertools：
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']))
以下是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
请注意，build议为这些提供一个帮助函数，因为prepend参数是静态的，每次调用都不会改变
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]]
这是一个非常肤浅的案件，但最好是安全的比对不起
