Python 非递归排列

Question

有人了解以下用于生成数字列表的所有排列的迭代算法吗？

我不明白 while len(stack) 循环中的逻辑。有人可以解释一下它是如何工作的吗？

# Non-Recursion
@param nums: A list of Integers.
@return: A list of permutations.

def permute(self, nums):
    if nums is None:
        return []
    nums = sorted(nums)
    permutation = []
    stack = [-1]
    permutations = []
    while len(stack):
        index = stack.pop()
        index += 1
        while index < len(nums):
            if nums[index] not in permutation:
                break
            index += 1
        else:
            if len(permutation):
                permutation.pop()
            continue

        stack.append(index)
        stack.append(-1)
        permutation.append(nums[index])
        if len(permutation) == len(nums):
            permutations.append(list(permutation))
    return permutations

我只是想理解上面的代码。

Answer 1

如您问题的评论部分所述，调试可能提供一种有助于理解代码功能的方法。但是，让我提供一个关于您的代码功能的高级视角。

首先，虽然没有对函数 permute 的递归调用，但您提供的代码实际上是递归的，因为它所做的只是保留自己的堆栈，而不是使用由OS 的内存管理器。具体来说，变量 stack 保持递归状态，可以这么说，即从一个递归调用传递到另一个递归调用。您可以，也许应该将 permute 函数中外部 while 循环的每次迭代视为递归调用。如果这样做，您将看到外部 while 循环帮助 'recursively' 以深度优先的方式遍历 nums 的每个排列。

注意到这一点，很容易弄清楚每个 'recursive call' 的作用。基本上，变量 permutation 保持 nums 的当前排列，该排列随着 while 循环的进行而形成。变量 permutations 存储找到的 nums 的所有排列。正如您可能观察到的，permutations 仅在 len(permutation) 等于 len(nums) 时更新，这可以被视为使用自定义堆栈实现的递归关系的基本情况。最后，内部 while 循环选择 nums 的哪个元素添加到正在形成的当前排列（即存储在变量 permutation 中）。

就是这样，真的。按照建议，您可以使用调试器弄清楚与维护 stack 相关的行到底做了什么。最后，让我重申一下，就我个人而言，我不会认为此实现是非递归的。碰巧的是，这个递归解决方案没有使用 OS 提供的抽象，而是保留了自己的堆栈。为了更好地理解正确的非递归解决方案如何，您可能会观察到下面提供的寻找 n^th 斐波那契数的问题的递归和迭代解决方案的差异。如您所见，非递归解决方案不保留堆栈，它不是将问题分成更小的实例（递归），而是从更小的解决方案构建解决方案。（动态规划）

def recursive_fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return recursive_fib(n-1) + recursive_fib(n-2)

def iterative_fib(n):
    f_0 = 0
    f_1 = 1
    for i in range(3, n):
        f_2 = f_1 + f_0
        f_0 = f_1
        f_1 = f_2
    return f_1

Answer 2

@ilim 的回答是正确的，应该是公认的答案，但我只是想补充一点不适合作为评论。虽然我想你正在研究这个算法作为练习，但应该指出，根据列表的大小，更好的方法可能是用户 itertools 的 permutations() 函数：

print [x for x in itertools.permutations([1, 2, 3])]

在我的机器上测试包含 11 个项目（39m 排列）的列表 itertools.permutations(x) 花费了 1.7 秒，但使用上面的自定义解决方案花费了 76 秒。但是请注意，对于 12 个项目（479m 排列），itertools 解决方案会因内存错误而崩溃。如果您需要有效地生成这种大小的排列，您最好使用本机代码。

Python 非递归排列

Python Non-recursive Permutation

python

algorithm

permutation