生成排列的递归函数正确打印每个排列但不能将其添加到列表中

Question

以下递归函数生成给定范围 (n) 中数字的所有排列。每个排列都以一个空列表开始。该函数将数字一个一个地相加并递归地生成部分排列。当排列达到长度 n 时，它已经完全增长并被打印出来。所有这些都正常工作。问题是我无法将每个排列附加到排列列表中。它只是添加一个空列表。是什么赋予了？顺带一提，我也在Java写了同样的代码，也遇到了同样的问题

permutations = []

def generate_permutations(n, perm=[]):
    """
    Recursive function to print all possible permutations of integers in range n.  
    :param perm: list representing a single permutation of integers in range(n)
    :param n: end of range(n) and length of each permutation
    """
    # base case: when a permutation reaches its full length, print it and move on:
    if len(perm) == n:
        print(perm)
        permutations.append(perm)  # does not work. Adds an empty list.
        return 
    # recursive case:
    for k in range(n):
        # if number k not already in the permutation, add it, generate permutations, and
        # then remove k so a new set of permutations can be generated.
        if k not in perm:
            perm.append(k)
            generate_permutations(n, perm)
            perm.pop()

以下调用生成以下输出：

generate_permutations(4)
print("______")
print(permutations)

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]
______
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]

Answer 1

您将 perm 附加到 permutations，然后使用 pop() 删除 perm 中的元素。这将删除 permutations 中的那些，因为它不是 permutations 中存在的 perm 的副本，而是对 perm 本身的引用。

references的概念，类似于C.[=27中的pointers =]

object_1 = object_2

将 object_2 的引用保存到 object_1 而不是副本，因此 object_2 中的任何更改都将反映在 object_1

中

使用copy.deepcopy()复制列表perm

工作代码：

import copy
permutations = []

def generate_permutations(n, perm=[]):
    """
    Recursive function to print all possible permutations of integers in range n.
    :param perm: list representing a single permutation of integers in range(n)
    :param n: end of range(n) and length of each permutation
    """
    # base case: when a permutation reaches its full length, print it and move on:
    if len(perm) == n:
        print(perm)
        permutations.append(copy.deepcopy(perm))  
        return
    # recursive case:
    for k in range(n):
        # if number k not already in the permutation, add it, generate permutations, and
        # then remove k so a new set of permutations can be generated.
        if k not in perm:
            perm.append(k)
            generate_permutations(n, perm)
            perm.pop()

generate_permutations(3)
print(permutations)

输出：

[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

生成排列的递归函数正确打印每个排列但不能将其添加到列表中

Recursive function to generate permutations correctly prints each permutation but can not add it to a list

python

algorithm

recursion

permutation