在Python中寻找给定字符串的所有可能排列

Question

我有一个字符串，我想从这个字符串中生成所有可能的排列，也就是改变字符的顺序。比如说：

x='stack'

我想要的结果是这样的一个列表，

l=['stack','satck','sackt'.......]

目前我在对字符串的字符列表进行循环，每次随机挑选两个字母，然后交换它们的位置，形成一个新的字符串，并把这个新字符串加入到一个集合里。根据字符串的长度，我在计算可能的排列数量，并继续循环，直到这个集合的大小达到限制为止。

我觉得应该有更好的方法来实现这个目标。

Answer 1

这里有另一种用最少代码实现字符串排列的方法，基于回溯算法。我们基本上是创建一个循环，然后每次交换两个字符。在循环内部，我们会使用递归。注意，只有当索引达到字符串的长度时，我们才会打印结果。

举个例子：字符串是ABC。这里的i是我们的起始点，也是递归的参数，j是我们的循环变量。

下面是一个可视化的帮助，展示了从左到右、从上到下的排列顺序。

代码如下：

def permute(data, i, length): 
    if i==length: 
        print(''.join(data) )
    else: 
        for j in range(i,length): 
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  
  

string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)

Answer 2

你可以用很少的代码得到所有的N!排列

def permutations(string, step = 0):

    # if we've gotten to the end, print the permutation
    if step == len(string):
        print "".join(string)

    # everything to the right of step has not been swapped yet
    for i in range(step, len(string)):

        # copy the string (store as array)
        string_copy = [character for character in string]

        # swap the current index with the step
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]

        # recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1)
        permutations(string_copy, step + 1)

Answer 3

itertools模块里有个很实用的方法叫做permutations()。文档里说：

itertools.permutations(iterable[, r])

这个方法会返回可迭代对象中元素的所有可能的长度为r的排列。

如果没有指定r或者r是None，那么r就会默认等于可迭代对象的长度，这样就会生成所有可能的完整排列。

排列的顺序是按照字典序的。所以，如果输入的可迭代对象是排好序的，生成的排列元组也会是有序的。

不过，你需要把排列好的字母连接成字符串。

>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms

['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']

如果你发现有重复的排列，可以试着把数据放到一个没有重复项的结构里，比如set：

>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360

感谢@pst指出，这其实不是我们传统意义上的类型转换，而更像是调用set()构造函数。