我无法使用 Python 中的递归函数进行排列

Question

我正在尝试制作一个递归函数，它打印给定集合的所有可能排列。

perm = []  # list to make permutations
S = {1,2,3,4}  # set of elements which have not used for the permutation yet
def make_perm():
if not S:
print(perm)
else:
for x in S:
perm.append(x)
S.remove(x)
make_perm()
perm.pop()
S.add(x)

make_perm()

然而，这个程序不起作用：它只输出[1,2,3,4]。原因是什么？

(添加(我希望程序输出如下。

> [1,2,3,4]
> [1,2,4,3]
> [1,3,2,4]
> [1,3,4,2]
︙

当它符合PyPy3(7.3.0(时，它只输出[1,2,3,4]。但当它符合Python3(3.8.2(时，它的输出如下。

> [1,2,3,4]
> [1,2,4,3]
> [1,3,2,4]
> [1,3,2,4]
> [1,3,4,2]
︙

有些输出是重复的。我很困惑，这些输出是不正确的和不同的：(.

Answer 1

问题是在对S进行迭代时对其进行了修改

for x in S.copy():
perm.append(x)
S.remove(x)
make_perm()
perm.pop()
S.add(x)

输出

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

注意，set不能保证订单，您应该使用list而不是

S = [1, 2, 3, 4]
for x in S[:]:
perm.append(x)
S.remove(x)
make_perm()
perm.pop()
S.append(x)

Answer 2

无论何时执行perm.append(x)，都会附加来自S的项，而不是排列，因此4次之后，S为空，您将获得[1, 2, 3, 4]。

请看这里如何生成列表的所有排列(在集合的情况下非常相似(。

Answer 3

没有回答这个问题，但我看到您使用的代码不符合这样一个函数应该如何工作的标准。目前，您的函数需要在函数外部设置两个字段。你不希望这样——函数应该只依赖于它们的参数。此外，您不应该打印所有排列，而应该return它们。这允许您以后处理排列。

def make_perm(iterable):
if not iterable: return null
else:
permutations = []
for elem in iterable:
#push to permutations
return permutations

s = {1, 2, 3, 4}
permutations = make_perm(s)
print(permutations)

如果您不想重新发明轮子，并且可以使用模块，请查看itertools.permutations