递归查找列表的所有组合 [英] Recursively find all combinations of list

问题描述

问题陈述

我想从列表(包括空列表)中排除所有可能的组合.

I want to get all possible combinations out of my list (including the empty list).

到目前为止，我的代码是:

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

我很确定我的退货有误.

I am pretty sure something with my return is not right.

非常感谢您的帮助.

推荐答案

可以通过以下方式找到递归关系:列表 l 的组合要么使用 l的最后一个元素，或者不是."

A recurrence relation can be found this way: "A combination of list l either uses the last element of l, or it doesn't."

因此，我们递归地找到子列表 l [:-1] 的组合(子列表包含除最后一个元素之外的所有元素)；然后我们添加或不添加最后一个元素.

So we find recursively the combinations of sublist l[:-1] (the sublist containing all elements except the last one); and then we either add or don't add the last element.

此递归需要一个基本情况.基本情况是:如果列表为空，则唯一的组合为空组合.

This recursion needs a base case. The base case is: if the list is empty, then the only combination is the empty combination.

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 循环可以很好地重复应用递归关系.

Iterative version

The recurrence relation is great, but there is no need for recursion; for-loops work very well to apply recurrence relations repeatedly.

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

这篇关于递归查找列表的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！