python - Why is the list appending the same element again and again?

Question

I am trying to solve this problem of finding the permutation of a given list using the code below. But, the list, final keeps appending the same thing again and again. It should return [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]] but instead it returns [[1,2,3],[1,2,3], [1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]. I have been trying to fix this for a while now and would really appreciate your help.

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.final = []
        l = 0 
        r = len(nums) -1 
        self.permutation(nums, l, r)
        return self.final

    def permutation(self, nums, l, r):
        if l == r:
            self.final.append(nums)
            # print(nums)
            print(self.final)
        else:
            for i in range(r+1):
                nums[l], nums[i] = nums[i], nums[l]
                self.permutation(nums, l+1, r)
                nums[l], nums[i] = nums[i], nums[l]

A = Solution()
A.permute(['1','2','3'])

标签： pythonrecursionpermutation

Answer 1

您就地更改列表，而不是每次都创建新列表。您的最终列表最终包含对同一列表的引用。

一个解决方法是写

def permutation(self, nums, l, r):
    if l == r:
        self.final.append(nums.copy())
        # instead of self.final.append(nums)

注意：itertools.permutations会为你做这项工作。

这篇文章可能有助于了解这里发生了什么。

正如评论中提到的：你仍然没有得到所有的排列。这可能对你有用：

def permutation(self, nums, k):
    r = [[]]
    for i in range(k):
        r = [[a] + b for a in nums for b in r if a not in b]
    self.final = r