递归查找列表的所有组合

Question

问题陈述

我想从我的列表中获取所有可能的组合（包括空列表）。

到目前为止我的代码是：

def combination(l):
    result = []
    for item in range(len(l)):
        cut_list = l[:item] + l[item + 1:]
        if len(cut_list) > 1:
            combination(cut_list)
        elif len(cut_list) == 1:
            result += cut_list
    return result


print(combination([1, 2, 3]))

我的输出是一个空列表

[]

我想要这个输出：

[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

我很确定我的退货有问题。

非常感谢任何帮助。

Answer 1

可以这样找到递归关系：“列表

l

的组合要么使用

l

的最后一个元素，要么不使用。”

因此我们递归地找到子列表

l[:-1]

的组合（子列表包含除最后一个元素之外的所有元素）；然后我们要么添加或不添加最后一个元素。

递归版本

这个递归需要一个基本情况。基本情况是：如果列表为空，则唯一的组合是空组合。

def combinations(l):
    if l:
      result = combinations(l[:-1])
      return result + [c + [l[-1]] for c in result]
    else:
      return [[]]

print(combinations([1,2,3]))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

迭代版本

仅仅因为我们有递归关系并不意味着我们需要递归；

for

-循环非常适合重复应用递归关系。

def combinations(l):
  result = [[]]
  for x in l:
    result = result + [c + [x] for c in result]
  return result

print(combinations([1,2,3]))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Answer 2

试试这个：

In [24]: import itertools

In [25]: l
Out[25]: [1, 2, 3]

In [26]: [sublist for item in [[list(x) for x in itertools.combinations(l,n)] for n in range(len(l)+1)] for sublist in item]
Out[26]: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Answer 3

这是我的做法（作为生成器）：

def combinations(aList):
    yield []
    for i,v in enumerate(aList,1):
        yield from ([v]+c for c in combinations(aList[i:]))
    

for combo in combinations([1,2,3]): print(combo)

[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

或作为列表生成器：

def combinations(aList):
    return [[]] + [ [v]+c for i,v in enumerate(aList,1) 
                          for c   in combinations(aList[i:]) ]

print( combinations([1,2,3]) )

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Answer 4

这就是你想做的事？

l = [3, 22, 10, 15, 32, 10, 5]


def f(ml: list):
    a = []
    for i1 in ml:
        for i2 in ml:
            if not i1 + i2 in a:
                a.append(i1 + i2)
    return a


print(f(l))

[6, 25, 13, 18, 35, 8, 44, 32, 37, 54, 27, 20, 42, 15, 30, 47, 64, 10]

Answer 5

您还应该传递您的

result

列表，如下所示。但我认为这个递归函数并没有达到你想要的效果。

def combination(l, result=[]):
    for item in range(len(l)):
        cut_list = l[:item] + l[item + 1:]
        if len(cut_list) > 1:
            combination(cut_list, result)
        elif len(cut_list) == 1:
            result += cut_list
    return result


print(combination([3, 22, 10, 15, 32, 10, 5]))

结果：

>>> python3 test.py 
[5, 10, 5, 32, 10, 32, 5, 10, 5, 15, 10, 15, 5, 32, 5, 15, 32, ...

无需递归即可获得所有组合/排列：

排列：

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

输出：

>>> python3 test.py 
()
(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)

组合（此机制与您问题中的描述相符）：

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

输出：

>>> python3 test.py 
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)

编辑：

当然，您可以从我下面的示例中创建一个函数，并且可以获得嵌套列表形式的结果。

代码：

import itertools

def combination(l):
    result = []
    for L in range(0, len(l)+1):
        for subset in itertools.combinations(l, L):
            result.append(list(subset))
    return result

print(combination([1, 2, 3]))

输出：

>>> python3 test.py 
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

编辑_2：

没有

itertools

模块的解决方案：

代码：

def combinations(return_len, iterable):
    if not return_len:
        return [[]]
    if not iterable:
        return []

    head = [iterable[0]]
    tail = iterable[1:]
    new_comb = [head + list_ for list_ in combinations(return_len - 1, tail)]

    return new_comb + combinations(return_len, tail)


input_list = [1, 2, 3]
result = []

for n in range(0, len(input_list) + 1):
    for single_result in combinations(n, input_list):
        result.append(single_result)

print(result)

输出：

>>> python3 test.py 
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]