如何在python中查找给定字符串的所有排列？

Question

我已经尝试过这种方法，但它出错了。因此，有什么想法可以解决此代码段吗？

def swap(seq, i , j):
    temp = 0
    temp = seq[i]
    seq[i] = seq[j]
    seq[j] = temp

def all_possible_strings(seq):
    list_of_results = []
    for i in range(len(seq)):
        for j in range(len(seq)):
            copy_of_seq = seq[:]

            swap(copy_of_seq, i ,j)

            list_of_results.append("".join(copy_of_seq))

    return list_of_results

这是输出：['abc'，'bac'，'cba'，'bac'，'abc'，'acb'，'cba'，'acb'，'abc']

Answer 1

您可以使用itertools.permutations：

itertools.permutations

输出：

import itertools

seq = 'abc'
list_of_results = [''.join(p) for p in itertools.permutations(seq)]
print(list_of_results)

Answer 2

您的算法可能无法考虑所有排列。

注意，对['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] 可以是任何索引对。但是，对于代码中的每个排列，都从原始字符串开始并应用一次交换。这可能无法获得所有排列。

假装以(i,j)开始。如果您想要反向排列ABCD，则将无法在一次交换中执行此操作。一次交换最多可以更改2个字符的位置，但是所有4个字符都必须位于不同的位置。

注意，对于大小为DCBA的列表，可能的(i,j)对的数量为n，这与预期的排列数n*n = n^2不同。在几乎所有情况下，n!都意味着肯定会缺少排列。

此外，您同时具有n! > n^2和(1,2)，这将导致ACBD，也将导致(2,1)。这就是为什么在最终排列列表中重复排列的原因。

P.S。在Python中，只需执行ACBD即可交换两个元素。

---

堆的算法

正确的实现是使用类似a,b = b,a的东西，这是对元素进行适当，更复杂的切换以获得所有排列的方法。

而不是每次都创建列表的新副本，而是继续在同一列表上进行交换，只要您按照算法指定的正确顺序进行排列，它将循环遍历所有排列。

我不会在这里详细介绍算法，因为资源在解释它方面做得很好。如果您确实需要显式的Python实现示例，则该示例也为Heap's algorithm。