如何获得列表元素的所有可能的组合?

我有一个包含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不同的元素,则为0n项目之间),并使用本地方法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']] 

在线试用:

http://ideone.com/COghfX

在@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]] 

这是一个非常肤浅的案件,但最好是安全的比对不起