使用回溯生成所有可能的排列

Question

我是编程新手，正在经历一些基本的回溯问题。其中之一是打印列表的所有可能排列。我从网上得到了以下代码。

def permutation(arr,size,n):
    if size == 1:
        print(arr)
        return
    for i in range(size):
        permutation(arr,size-1,n)
        if size & 1:
            arr[0],arr[size-1] = arr[size-1],arr[0]
        else:
            arr[i],arr[size-1] = arr[size-1],arr[i]

这工作正常，它为输入 arr = [1,2,3]

打印了以下输出

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

现在我想将所有这些可能的排列存储到一个不同的数组中，为此修改了代码。

 ans = []
 def permutation(arr,size,n):
    if size == 1:
        ans.append(arr)
    for i in range(size):
        permutation(arr,size-1,n)
        if size & 1:
            arr[0],arr[size-1] = arr[size-1],arr[0]
        else:
            arr[i],arr[size-1] = arr[size-1],arr[i]

但是当我打印列表时，它打印了这个。

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

我在这里做错了什么？如何将所有可能的排列存储到列表中？

Answer 1

原始答案，没有回答问题（见编辑）

回答“我在这里做错了什么？”问题。

你有

    if size == 1:
        print(arr)
        return

在第一个代码中，但是

    if size == 1:
        ans.append(arr)

尝试：

    if size == 1:
        ans.append(arr)
        return

它应该按预期工作

编辑：

感谢@superbrain 批评，确实不行，我对OP中的代码正确性太乐观了

所以“我在这里做错了什么？”的答案是这条线

        ans.append(arr)

你每次附加同一个列表实例，所以你以相同对象的列表结尾

类似这样的场景：

list1 = [1,2,3]
list2 = []
list2.append(list1)
list2.append(list1)
print(list2) # [[1, 2, 3], [1, 2, 3]]
list1[2] = 9
print(list2) # [[1, 2, 9], [1, 2, 9]]

Answer 2

回溯是一种通用算法，“它逐步构建解决方案的候选方案，并在确定候选方案不可能完成有效解决方案后立即放弃每个部分候选方案（“回溯”）。” （维基百科）。

所以，基本上，您所做的就是逐步构建所有排列。一旦构建了一个排列，就回溯并构建另一个排列，依此类推，直到生成所有 n!可能的排列，比如说，在 n 个符号上。

示例：n=3，S={1,2,3}。

你从 1 开始。然后你向前移动并选择 2（因为 1 已经被选择），然后你选择 3。此时你已经构建了第一个排列 123。然后你回溯 select 3而不是2，然后select 2，你有132。你再次回溯，但是你已经使用了2和3，所以你再次回溯（向上一级where），并选择2而不是1 , 然后你 select 1, 最后是 3, 所以你有 213.

Answer 3

问题是您总是将对 arr 对象（它是一个列表）的同一实例的引用附加到 ans 列表。有关类似情况，请参阅 this question。

您在第一个代码中没有这个问题，因为您只是在每次排列时打印列表。但是在第二个代码中，您在每次递归时操作 相同的 列表，当您位于递归树的顶部时，您会返回原始列表 ([1, 2, 3]).

要解决此问题，您可以将您的列表的 深拷贝 添加到 ans:

def permutation(arr, size, n):
    if size == 1:
        # ans.append(arr)

        # this copies every element of arr into a 
        # new list and then appends the new list to ans.
        ans.append([e for e in arr]) 

    for i in range(size):
        permutation(arr, size-1, n)
        if size & 1:
            arr[0], arr[size-1] = arr[size-1], arr[0]
        else:
            arr[i], arr[size-1] = arr[size-1], arr[i]

使用回溯生成所有可能的排列

Generation of all possible permutations using backtracking

python

recursion

permutation

backtracking