基于显式栈实现{1,2,…,n}全排列的非递归算法方案咨询

题目要求 #

本题来自Goodrich等人所著《Data Structures and Algorithms in Python》，核心要求是使用显式栈、以非递归方式枚举数字{1,2,...,n}的所有排列，题目原文为：

描述一种使用显式栈枚举数字{1, 2, ..., n}所有排列的非递归算法。

题目给出的提示为：

使用栈将问题归约为枚举数字{1, 2, ..., n-1}的所有排列。

初始实现思路与疑问 #

最初的实现逻辑如下：

• 先将n、n-1、…依次入栈直到1
• 初始化存储全排列的列表，先存入1的全排列（即仅包含单个元素1的列表）
• 依次弹出栈中元素，将当前弹出值插入到列表内每个已有排列的所有可能位置，生成更长的排列集合
• 栈空时即可得到1到n的所有全排列

存在的疑问：该思路不确定是否符合题目提示要求，比如方案使用了提示未提及的额外列表存储中间排列结果，希望找到更贴合提示归约思路的实现方式。

初始思路实现代码 #

def permutations(n):
    s = MyStack()
    perms = [[]]
    while n > 0:
        s.push(n)
        n -= 1
    
    total = 1
    factor = 1

    while not s.is_empty():
        val = s.pop()

        total *= factor
        factor += 1

        prev = perms
        perms = [None] * total
        idx = 0

        for perm in prev:
            for pos in range(len(perm) + 1):
                perms[idx] = [*perm[:pos], val, *perm[pos:]]
                idx += 1

    for perm in perms:
        print(perm)

贴合提示的显式栈版本实现 #

参考btilly的思路实现的版本完全依托显式栈模拟递归归约过程，不需要额外列表存储全量中间排列结果，在回溯遍历过程中直接输出所有排列，代码如下：

def permutations_explicit_stack(items):
    items = list(items)
    n = len(items)
    s = MyStack()
    i = 0
    perm = []
    
    while i < n:
        perm.append(items.pop(0))
        s.push(i)
        i = 0
        
        if len(items) == 0:
            print(perm)
            
            while i == len(items) and s:
                i = s.pop()
                items.append(perm.pop())
                i += 1

内容的提问来源于stack exchange，提问作者Ruperrrt