python - 使用堆栈排列列表

Question

我正在尝试找到一种无需递归或使用 itertools 即可枚举数字列表的所有组合的方法。我想出了一个可行的解决方案，但我认为它最终变成了一个递归函数。我是 Python 的新手，不确定如何在没有递归的情况下完成这项工作。

感谢任何帮助，因为我认为我仍然看不出两者之间的区别。

result = []

def permutation(li):
    if len(li) == 1:
        result.append(li[0])
        print (result)
        result.pop()
        return

    for i in range(0,len(li)):
        result.append(li[i])
        permutation(li[:i] + li[i+1:])
        result.pop()    

permutation([1,2,3])

Answer 1

在不使用递归的情况下，想出一种“就像那样”产生所有排列的算法并不是那么直观。

但是存在几种不同的此类算法。看看Heap's algorithm例如:

def permutation(li):
    n = len(li)
    c = [0] * n

    print(li)
    i = 1
    while i < n:
        if c[i] < i:
            j = c[i] if i % 2 else 0
            li[j], li[i] = li[i], li[j]
            print(li)
            c[i] += 1
            i = 1
        else:
            c[i] = 0
            i += 1