无法跟踪为什么字符串排列未附加到数组排列的全局变量中

Question

我正在尝试编写字符串排列问题的代码。我有一个整数列表，而不是字符串，例如 [1,2,3]。我必须打印出列表的所有可能排列。但是，我的代码存在一些我无法弄清楚的问题。不知何故，基本情况中的行 if not in words 只命中一次。我试图从过去一小时中弄清楚这一点。任何帮助，将不胜感激！。 TIA 这是代码

words = list()  
def permute(nums):
    if len(nums) == 0:
        return None

    l = 0
    r = len(nums)

    permute_helper(nums,0,r)

def permute_helper(nums,start,end):
    current = 0
    if start == end-1:
        if not nums in words:
            print 'appended'
            words.append(nums)   
    else:
        for current in range(start,end):
            temp = nums[start]
            nums[start] = nums[current]
            nums[current] = temp
            #Recursive call
            permute_helper(nums,start+1,end)
            temp = nums[start]
            nums[start] = nums[current]
            nums[current] = temp

permute([1,2,3])
print words

Answer 1

错误是您不断修改同一个列表nums，所以您最终只得到一个已修改但未记录修改的副本。

变化：

words.append(nums)

至：

words.append(nums[:])

这将创建 nums 和 "freeze" 当前状态的副本。

评论： 您可以用更 Pythonic 的方式进行交换，而不是：

temp = nums[start]
nums[start] = nums[current]
nums[current] = temp

做：

nums[start], nums[current] = nums[current], nums[start]

Answer 2

您每次都附加相同的列表。难怪它已经存在 (in words)。

换句话说，您收集的不是每个不同的排列，而是对 nums 的引用。因此，后续排列反映在 words 中。这就是可变性的祸害。

一个解决方案是复制当前排列：

words.append(nums[:])

顺便说一句，pythonic 交换是：

a, b = b, a   # no need for tmp

此外，无需重新设置current。

无法跟踪为什么字符串排列未附加到数组排列的全局变量中

Unable to track why string permutations are not being appended in a global variable for array permutations

python

string

algorithm

backtracking

recursive-backtracking