在python中查找给定字符串的所有可能排列

Question

我有一个字符串。我想通过更改其中字符的顺序从该字符串生成所有排列。例如，说：

 x='stack'

我想要的是这样的列表，

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

目前我正在迭代字符串的列表转换，随机选择 2 个字母并将它们转置以形成一个新字符串，并将其添加到 l 的设置转换中。根据字符串的长度，我正在计算可能的排列数并继续迭代，直到设置大小达到限制。必须有更好的方法来做到这一点。

原文由 Nihar Sarangi 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

itertools 模块有一个有用的方法，称为 permutations()。 文件 说：

itertools.permutations(iterable[, r])

返回 iterable 中元素的连续 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() 构造函数的调用。

原文由 machine yearning 发布，翻译遵循 CC BY-SA 3.0 许可协议

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)

原文由 illerucis 发布，翻译遵循 CC BY-SA 3.0 许可协议