python - Generating all possible combinations of a list, "itertools.combinations" misses some results

Question

Given a list of items in Python, how can I get all the possible combinations of the items?

There are several similar questions on this site, that suggest using itertools.combinations, but that returns only a subset of what I need:

stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print(subset)

()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)

As you see, it returns only items in a strict order, not returning (2, 1), (3, 2), (3, 1), (2, 1, 3), (3, 1, 2), (2, 3, 1), and (3, 2, 1). Is there some workaround for that? I can't seem to come up with anything.

score 40 · Accepted Answer

使用itertools.permutations：

>>> import itertools
>>> stuff = [1, 2, 3]
>>> for L in range(0, len(stuff)+1):
        for subset in itertools.permutations(stuff, L):
                print(subset)
...         
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
....

帮助itertools.permutations：

permutations(iterable[, r]) --> permutations object

Return successive r-length permutations of elements in the iterable.

permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

score 12 · Accepted Answer

您可以使用这个简单的代码在 python 中生成列表的所有组合

import itertools

a = [1,2,3,4]
for i in xrange(1,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)]

score 8 · Accepted Answer

您是否正在寻找itertools.permutations？

从help(itertools.permutations),

Help on class permutations in module itertools:

class permutations(__builtin__.object)
 |  permutations(iterable[, r]) --> permutations object
 |  
 |  Return successive r-length permutations of elements in the iterable.
 |  
 |  permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

示例代码：

>>> from itertools import permutations
>>> stuff = [1, 2, 3]
>>> for i in range(0, len(stuff)+1):
        for subset in permutations(stuff, i):
               print(subset)


()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

来自维基百科，排列和组合之间的区别：

排列：

非正式地，一组对象的排列是这些对象按特定顺序排列。例如，集合{1,2,3}有六个排列，分别是(1,2,3), (1,3,2), (2,1,3), (2,3,1) , (3,1,2) 和 (3,2,1)。

组合：

在数学中，组合是从更大的组中选择几个事物的一种方式，其中（与排列不同）顺序无关紧要。

score 4 · Accepted Answer

itertools.permutations将是你想要的。根据数学定义，顺序无关紧要combinations，含义(1,2)被认为与相同(2,1)。而对于permutations，每个不同的排序都算作一个唯一的排列，因此(1,2)和(2,1)是完全不同的。

score 4 · Accepted Answer

这是一个没有 itertools 的解决方案

首先让我们定义一个0和1s 的指示向量与子列表之间的转换（1如果项目在子列表中）

def indicators2sublist(indicators,arr):
   return [item for item,indicator in zip(arr,indicators) if int(indicator)==1]

接下来，定义一个从数字到其二进制向量表示的映射0（2^n-1使用字符串的format函数）：

def bin(n,sz):
   return ('{d:0'+str(sz)+'b}').format(d=n)

我们剩下要做的就是迭代所有可能的数字，然后调用indicators2sublist

def all_sublists(arr):
  sz=len(arr)
  for n in xrange(0,2**sz):
     b=bin(n,sz)
     yield indicators2sublist(b,arr)

score 0 · Accepted Answer

我假设您希望所有可能的组合都作为值的“集合”。这是我写的一段代码，可能有助于给你一个想法：

def getAllCombinations(object_list):
    uniq_objs = set(object_list)
    combinations = []
    for obj in uniq_objs:
        for i in range(0,len(combinations)):
            combinations.append(combinations[i].union([obj]))
        combinations.append(set([obj]))
return combinations

这是一个示例：

combinations = getAllCombinations([20,10,30])
combinations.sort(key = lambda s: len(s))
print combinations
... [set([10]), set([20]), set([30]), set([10, 20]), set([10, 30]), set([20, 30]), set([10, 20, 30])]

我认为这有n！时间复杂度，所以要小心。这可行，但可能不是最有效的

score -2 · Accepted Answer

只是想我会把它放在那里，因为我不能很好地处理每一个可能的结果，并记住我只有最原始的最基本的知识，当涉及到 python 时，可能有一个更优雅的解决方案......（也是借口可怜的变量名

测试 = [1, 2, 3]

测试2= [0]

n = -1

def testingSomethingElse（数字）：

try:

    testing2[0:len(testing2)] == testing[0]

    n = -1

    testing2[number] += 1

except IndexError:

    testing2.append(testing[0])

而真：

n += 1

testing2[0] = testing[n]

print(testing2)

if testing2[0] == testing[-1]:

    try:

        n = -1

        testing2[1] += 1

    except IndexError:

        testing2.append(testing[0])

    for i in range(len(testing2)):

        if testing2[i] == 4:

            testingSomethingElse(i+1)

            testing2[i] = testing[0]

我逃脱了 == 4 因为我正在使用整数，但您可能必须相应地修改它......

python - Generating all possible combinations of a list, "itertools.combinations" misses some results

7 回答 7

这是一个没有 itertools 的解决方案

Related

Reference