在 python 中使用递归将子序列存储在列表列表中

Question

这听起来很简单，我尝试搜索解决方案但找不到，因此发布了问题。感谢您的帮助，提前致谢。

我正在尝试使用递归打印 python 中给定 list/string 的所有子序列。以下是我期望的输出：

给定的输入列表：[1,3,2] 输出列表：[[],[1],[3],[2],[1,2],[1,3],[3,2],[1,3,2]]

这是我试过的：

def printSubsequences(ind,ans,l,n):
    final_ans = []
    if ind == n:
        return ans
    else:
        ans.append(l[ind])
        final_ans.extend(printSubsequences(ind+1,ans,l,n))
        
        ans.pop()
        
        final_ans.extend(printSubsequences(ind+1,ans,l,n))
        return final_ans
       
print(printSubsequences(0,[],[1,3,2],3))

Output of above code: [1, 3, 2, 1, 3, 1, 2, 1, 3, 2, 3, 2]

输出部分正确，因为它不包含 []（空子集），但我希望它采用上述指定格式。我也试过 append 方法，但那是 Output : [[[[], []], [[], []]], [[[], []], [[], []]]].

我不明白我在这里做错了什么，有人可以解释一下 - 为什么 append 失败而 extend 正常工作，以及如何获得我想要的输出？

Answer 1

您运行进入了这个经典的 python 陷阱：

List of lists changes reflected across sublists unexpectedly

当您将 ans 附加到结果列表时，它始终是对同一列表 ans 的引用，而不是副本。因此，当您调用 ans.pop() 时，您删除了该列表的最后一个元素，并且它在所有子序列中都被删除了。试试这个代码：

a = [2]
b = [a, a, a]
print(b) # [[2], [2], [2]]
a.pop()
print(b) # [[], [], []]

解决方法是采用更实用的样式，从不就地修改 ans 列表，而是在递归调用需要时构建新列表：

def subsequences(ind,ans,l,n):
    final_ans = []
    if ind == n:
        return [ans]
    else:
        final_ans.extend(subsequences(ind+1,ans + [l[ind]],l,n))
        final_ans.extend(subsequences(ind+1,ans,l,n))
        return final_ans

>>> subsequences(0, [], [1,2,3], 3)
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

显着修改：

我将函数重命名为 subsequences 而不是 printSubsequences，因为它不打印；
我修正了基本情况，应该是 return [ans]，而不是 return ans；
我在递归调用中用 + 替换了对 ans.append 和 ans.pop 的调用。

在 python 中使用递归将子序列存储在列表列表中

Store Subsequences in list of lists using recursion in python

python-3.x

recursion

subsequence