阵列的排列-Python

Question

我正在尝试获取输入阵列的所有排列，由于某种原因，无论我尝试多么努力，都无法获得正确的答案。以下是样本输入

输入：array = [1，2，3]

输出：[[1,2,3]，[1,3,2]，[2,1，[2,1， 3]，[2,3,1]，[3,1,2]，[3,2,1]]

我试图通过一直到那里的基本案例来递归地做到这一点仅是一个元素。然后，我将一次添加一个元素，然后将其放在数组的每个可能位置。以下是我

def get_permutations(array):
    # Base case
    if len(array) <= 1:
        return [array]

    all_chars_except_last = array[:-1]
    last_char = array[-1]

    permutations_of_all_char_except_last = get_permutations(all_chars_except_last)

    # Put the last char in all possible positions for each of the above permutations
    permutations = []
    for permutation_of_all_chars_except_last in permutations_of_all_char_except_last:
        for position in range(len(all_chars_except_last)+1):
            permutation = permutation_of_all_chars_except_last.insert(position, last_char)
        
            permutations.append(permutation)
    return permutations

关于我的代码的去向的递归尝试建议！我只是想在这个正在编码的美好世界中提高自己的技能！

Answer 1

代码的问题在于insert方法不会返回列表，而是none。此外，insert突变您调用的列表，这也是不希望的。

因此，您需要用创建新列表的语句替换该语句而不突变原始列表：

permutation = permutation_of_all_chars_except_last[:position] + [last_char] + permutation_of_all_chars_except_last[position:]

或者，或者首先取一个副本，然后调用insert：

permutation = permutation_of_all_chars_except_last[:]
permutation.insert(position, last_char)

Answer 2

由于您是出于学习目的而这样做的，并提高了您的编码技能，因此我会根据发电机添加其他实现。大多数传统递归实现的问题在于，它可以随着阵列长度的增加而迅速地吞噬所有记忆。

def get_permutations(array):
    if len(array) <= 1:
        yield array
    else:
        for perm in get_permutations(array[1:]):
            for i in range(len(array)):
                yield perm[:i] + array[0:1] + perm[i:]

置换阵列将在消费时实现，因此将保留内存。

list(get_permutations([1,2,3]))
# [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

此外，在ietrtools之类的模块中存在有效的实现：

import itertools as it
list(it.permutations([1, 2, 3]))
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]