我试图编写自己的代码来打印字符串的所有排列(因为我是初学者，想要练习和熟悉)。但是，当我将字符串转换为函数外部的列表时，它不起作用，而如果我在内部转换它并在递归之前将其转换回字符串，它就会起作用…
def permutations(mesg, l, r):
msg = list(mesg)
if l == r-1:
print("".join(msg))
else:
for i in range(l, r):
msg[i], msg[l] = msg[l], msg[i]
permutations("".join(msg), l+1, r)
message = "ABC"
permutations(message, 0, len(message))
input("press X to exti: ")
，输出为:美国广播公司ACBBACBCA出租车CBA
def permutations(msg, l, r):
if l == r-1:
print("".join(msg))
else:
for i in range(l, r):
msg[i], msg[l] = msg[l], msg[i]
permutations(msg, l+1, r)
message = "ABC"
permutations(list(message), 0, len(message))
input("press X to exti: ")
，输出为:美国广播公司ACB出租车CBA美国广播公司ACB
l和I变量的进度:# 00,11,12,01,11,12,02,11,12。第一个数字是l，另一个是i，每一对数字都在递归之前在for循环中打印。
这种行为的原因是列表是可变的，而递归需要一个自相似的属性:递归调用的输入不能与它的父状态混淆，否则你会得到一个与调用者最初在for循环中工作的列表不同的列表，一旦子进程完成工作，控制返回到父进程。
顶部的代码违反了这条规则:每次循环都交换列表中的元素，但没有任何东西被恢复，因此所有通过调用叶节点的递归操作都会污染未来通过父循环的行程。
list()通过实现不变性解决了这个问题，但它不是最注重性能的方法，因为您在每个调用帧上复制整个列表。另一种典型的方法通常是"撤消"。每个子调用后的交换操作返回:
def permutations(lst, left, right):
if left == right - 1:
print("".join(lst))
else:
for i in range(left, right):
lst[i], lst[left] = lst[left], lst[i]
permutations(lst, left + 1, right)
# undo the swap to restore the list
lst[i], lst[left] = lst[left], lst[i]
if __name__ == "__main__":
permutations(list("abc"), 0, 3)
一些额外的建议:
- PEP-8禁止使用
l作为变量名，因为它太容易混淆1或i。 right只是len(lst)的别名。只需调用len，即可简化您的状态。只有当它是一个可移动索引时才使用right，比如二进制搜索。print("".join(lst))优于yield lst[:]。任何排列函数基本上都应该像itertools.permutations那样返回一个生成器。返回列表的列表也比print的副作用要好得多，后者基本上使函数单一用途，并且对于任何想要应用更多操作的编程都无用(并且您通常会这样做;print在这里是个死胡同)。- 避免字符串连接操作以保持函数的泛型。如果打电话的人想这样做，就让他们去做吧。没有理由错误的
[1, 2, 3]作为参数，结果应该仍然是一个列表，而不是"123", ...。 left(实际上是i)可以作为默认参数。
把它放在一起:
def permutations(lst, i=0):
if i == len(lst) - 1:
yield lst[:]
else:
for j in range(i, len(lst)):
lst[i], lst[j] = lst[j], lst[i]
yield from permutations(lst, i + 1)
lst[i], lst[j] = lst[j], lst[i]
if __name__ == "__main__":
for p in permutations(list("abc")):
print("".join(p))
(不用说，永远不要真正使用这段代码，使用itertools.permutations——它快得多)