这个递归程序每次都会给出不同的输出

Question

我在 Michael Goodrich 的书中发现了一种生成集合排列的算法。

def puzzle(k,S,U):
    for e in U:
        S.append(e)
        U.remove(e)
        if k == 1:
            print(S)
        else:
            puzzle(k-1,S,U)
        U.add(e)
        S.pop()
k = 3
S = []
U = {'a','b','c'}
print(puzzle(k,S,U))

有趣的是，这个程序用相同的输入给我不同的输出，任何人都可以解释我为什么会这样，我可以改变什么来使这个算法起作用？

Answer 1

Python 中的集合迭代在顺序上并不一致，如评论中所述。如果您必须保持输出的一致性，您可以使用

OrderedDict

来代替。然而，随着输入大小的增加，这将带来显着的性能缺陷。

---

from collections import OrderedDict

def puzzle(k,S,U: OrderedDict):
    for e in list(U.keys()):
        S.append(e)
        U.pop(e)
        if k == 1:
            print(S)
        else:
            puzzle(k-1,S,U)
        U[e] = e
        S.pop()

k_ = 3
S_ = []
U_ = OrderedDict(); U_['a']='a'; U_['b']='b'; U_['c']='c'
print(puzzle(k_,S_,U_))