递归查找列表的所有组合

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