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

Question

我有一个字符串。我想通过改变其中字符的顺序来生成该字符串的所有排列。例如，假设：

x='stack'

我想要的是这样的一个列表：

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

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

- Nihar Sarangi

Answer 1

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']

注：这是一个由单词“stack”重新排列组成的列表。

如果您发现有重复的问题，请尝试将数据放入没有重复项的结构中，例如set。

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

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

- machine yearning

---

Nit: set(...)并不是 "cast"，而是生成（和产生）表示输入集合的集合：一旦生成，它就与输入集合没有关联（并且是一个不同的对象，而不仅仅是不同的视图）。 - user166390

类型转换。正如你所指出的那样，它可能与仅仅是视图不同，我喜欢尝试保持概念分离以避免混淆。虽然我在第一条评论中应该明确提到“强制转换”，但我认为set是一个函数：list -> set。 - user166390

@pst：从文档中可以看到： 内置函数bool()可用于将任何值转换为布尔值，如果该值可以被解释为真值 这意味着它是一种强制类型转换，尽管存在明显的数据丢失和结构改变。但现在它像一个布尔值一样“嘎嘎叫”。 - machine yearning

我认为，bool 是一个根据输入值而评估为布尔值（True/False）的函数。我觉得在这里使用"cast"是多余且误导性的。 - user166390

作为一个有趣的更新，文档已经更改为说内置函数bool()可用于将任何值转换为布尔值，特别是转换而不是强制转换。这发生在此讨论之后的发布中，这让我相信这个讨论导致了文档的变化！ - machine yearning

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

---

很好。完美运作。 - kishorer747

我只是稍微修改了一下，如果i == step，我们不需要交换变量。 - work_in_progress

运行时间复杂度为O(n!)，因为存在n!种排列方式。 - Adrienne

你为什么使用 step == len(string) 而不是 step == len(string) - 1？ - tulians

因为这样最后的两个项目永远不会被交换。尝试使用“abc”直到b和c被交换。 - Roman Riesen

如果在if语句中没有else或return，它不是会毫无意义地运行for循环吗？我猜for循环就像下面这样：for i in range(x, x)，这样它将不会执行任何操作；聪明，不错的技巧。虽然可读性较低，但让我想起了门控，即使它并不是真正的门控，下面的代码仍会运行，只是不会做任何事情。 - CTS_AE

Answer 3

这是一种基于回溯算法的用最小代码实现字符串排列的另一种方法。我们基本上创建一个循环，每次交换两个字符，循环内部进行递归。注意，只有当索引达到字符串长度时才会打印。例如：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)

- grepit

---

提一下这是“回溯算法”范式的基础可能会有帮助。 - AruniRC

更多信息，相同/类似的代码：https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ 不过我更喜欢你的例子，因为有图形示例 ;) - CTS_AE

这是理解的好方法，但代码计算成本高，无法通过Codewars测试。 - Ali Waqas

Answer 4

Stack Overflow的用户已经发布了一些强大的解决方案，但我想展示另一个解决方案。我发现这个更直观。

对于给定的字符串，我们可以按照以下算法进行递归（伪代码）：

permutations = char + permutations(string - char) for char in string

希望能对某些人有所帮助！

def permutations(string):
    """
    Create all permutations of a string with non-repeating characters
    """
    permutation_list = []
    if len(string) == 1:
        return [string]
    else:
        for char in string:
            [permutation_list.append(char + a) for a in permutations(string.replace(char, "", 1))]
    return permutation_list

- BushMinusZero

---

无法处理存在重复字符的情况（如str.replace），例如：rqqx。 - sanjay

使用以下代码：[permutation_list.append(char + a) for a in permutations(string.replace(char, "", 1))] - user3761855

Answer 5

这里有一个简单的函数来返回唯一的排列组合：

def permutations(string):
    if len(string) == 1:
        return string

    recursive_perms = []
    for c in string:
        for perm in permutations(string.replace(c,'',1)):
            recursive_perms.append(c+perm)

    return set(recursive_perms)

- ArashkG

---

1. 你打错了：revursive_perms -> recursive_perms。
2. 如果recursive_perms是一个集合而不是你在返回语句中转换为集合的列表，那么它可以节省RAM和时间。
3. 使用字符串切片来构建permutations递归调用的参数会更有效率，而不是使用.replace方法。
4. 将变量名命名为string不是个好主意，因为它会遮盖标准的string模块名称。

- PM 2Ring

Answer 6

itertools.permutations很好用，但是它无法很好地处理包含重复元素的序列。这是因为它在内部对序列索引进行排列组合，并且忽略序列项的值。

当然，可以通过将itertools.permutations的输出通过集合进行过滤以消除重复项，但它仍会浪费时间生成那些重复项，而且如果基本序列中有几个重复元素，那么就会有很多重复项。此外，使用集合来保存结果会浪费RAM，抵消了首先使用迭代器的好处。

幸运的是，还有更高效的方法。下面的代码使用了14世纪印度数学家Narayana Pandita的算法，可以在排列组合的维基百科文章中找到。这种古老的算法仍然是已知的最快的按顺序生成排列组合的方法之一，而且它非常健壮，可以正确处理包含重复元素的排列组合。

def lexico_permute_string(s):
    ''' Generate all permutations in lexicographic order of string `s`

        This algorithm, due to Narayana Pandita, is from
        https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

        To produce the next permutation in lexicographic order of sequence `a`

        1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, 
        the permutation is the last permutation.
        2. Find the largest index k greater than j such that a[j] < a[k].
        3. Swap the value of a[j] with that of a[k].
        4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
    '''

    a = sorted(s)
    n = len(a) - 1
    while True:
        yield ''.join(a)

        #1. Find the largest index j such that a[j] < a[j + 1]
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return

        #2. Find the largest index k greater than j such that a[j] < a[k]
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break

        #3. Swap the value of a[j] with that of a[k].
        a[j], a[k] = a[k], a[j]

        #4. Reverse the tail of the sequence
        a[j+1:] = a[j+1:][::-1]

for s in lexico_permute_string('data'):
    print(s)

输出

aadt
aatd
adat
adta
atad
atda
daat
data
dtaa
taad
tada
tdaa

当然，如果你想将生成的字符串收集到一个列表中，你可以这样做：

list(lexico_permute_string('data'))

在最近的Python版本中：

[*lexico_permute_string('data')]

- PM 2Ring

---

讲解得非常清晰明了。 - lmao

Answer 7

这里有另一种方法，不同于@Adriano和@illerucis发布的方法。这种方法具有更好的运行时间，您可以通过测量时间来验证：

def removeCharFromStr(str, index):
    endIndex = index if index == len(str) else index + 1
    return str[:index] + str[endIndex:]

# 'ab' -> a + 'b', b + 'a'
# 'abc' ->  a + bc, b + ac, c + ab
#           a + cb, b + ca, c + ba
def perm(str):
    if len(str) <= 1:
        return {str}
    permSet = set()
    for i, c in enumerate(str):
        newStr = removeCharFromStr(str, i)
        retSet = perm(newStr)
        for elem in retSet:
            permSet.add(c + elem)
    return permSet

对于任意字符串 "dadffddxcf"，排列库需要 1.1336 秒，这种实现需要 9.125 秒，而 @Adriano 和 @illerucis 版本需要 16.357 秒。当然你仍然可以进行优化。

- Rooky

Answer 8

这是稍微改进过的代码，用于返回一个字符串 s 中所有不重复字符的排列列表（不一定按字典顺序），而不使用itertools：

illerucis 的代码。

def get_perms(s, i=0):
    """
    Returns a list of all (len(s) - i)! permutations t of s where t[:i] = s[:i].
    """
    # To avoid memory allocations for intermediate strings, use a list of chars.
    if isinstance(s, str):
        s = list(s)

    # Base Case: 0! = 1! = 1.
    # Store the only permutation as an immutable string, not a mutable list.
    if i >= len(s) - 1:
        return ["".join(s)]

    # Inductive Step: (len(s) - i)! = (len(s) - i) * (len(s) - i - 1)!
    # Swap in each suffix character to be at the beginning of the suffix.
    perms = get_perms(s, i + 1)
    for j in range(i + 1, len(s)):
        s[i], s[j] = s[j], s[i]
        perms.extend(get_perms(s, i + 1))
        s[i], s[j] = s[j], s[i]
    return perms

- Adriano

Answer 9

所有可能的单词（使用堆栈）

from itertools import permutations
for i in permutations('stack'):
    print(''.join(i))

permutations(iterable, r=None)

返回可迭代对象中长度为 r 的连续排列组合。

如果未指定 r 或 r 为 None，则默认为可迭代对象的长度，并生成所有可能的完整排列组合。

排列组合按词典序排序。因此，如果输入的可迭代对象已排序，则排列元组将按排序顺序生成。

元素根据其位置而不是值被视为唯一。因此，如果输入元素是唯一的，则每个排列中不会有重复值。

- Deepak Raj

Answer 10

请参考itertools.combinations或itertools.permutations。

- Brian Cain

---

组合对他的问题无关，他是交换字母，这意味着顺序很重要，也就是说只有排列。 - machine yearning