python - C++ 或 Python 中字符串的所有排列的算法

Question

我需要在 c++ 或 python 中编写一个函数，它获取一个字符串并打印所有可以加扰的选项。例如 - scramble("abc") 将打印 -

abc
acb
bac
bca
cab
cba

当然，长度为 3 的不仅仅是单词。

Answer 1

在 Python 中，您可以使用来自 itertools 的便捷排列函数。

from itertools import permutations

def scrambles(word):
    return [''.join(permutation) for permutation in permutations(word)]

或者，这是一个明确说明的递归置换算法：

def permutations(word):

    if len(word) == 1:
        # the word is one letter long, so this is the base case; there is only one permutation
        return [word]

    # recursively get all permutations of the word after its first letter
    subword_perms = permutations(word[1:])

    # insert the first letter at all possible positions in each of the possible permutations of the rest of the letters
    first_letter = word[0]
    perms = []
    for subword_perm in subword_perms:
        for i in range(len(subword_perm)+1):
            perm = subword_perm[:i] + first_letter + subword_perm[i:]

            # test to make sure permutation wasn't already found (which is possible if some letters are duplicated within the word)
            if perm not in perms:
                perms.append(perm)
    return perms

Answer 2

这是一个较短的递归函数，用于查找字符串中字母的所有排列：

def gen_perms(n,text):
    if n == 1:
        return {a for a in text}
    temp = {a + b
           for a in text
           for b in gen_perms(n-1,text)}
    return temp

n是您要生成的单词/集合的长度

text是您要使用的字母集。

我使用集合是因为​​它们没有重复的条目；只有独特的元素。

要解释该算法，请从 n=1 的基本情况开始。通过返回每个字母来处理这种特殊情况。

    if n == 1:
        return {a for a in text}

例如，当n=1 时，text='yz'：

>>> perms = gen_perms(1,'yz')
>>> print len(perms)
2
>>> print sorted(perms)
['y', 'z']

当 n=2 时，我们递归地运行该函数，因此请考虑上面的基本情况在这一行返回：

           {a + b
           for a in text
           for b in gen_perms(n-1,text)}

并将每个可能的字母添加到上面。我将用text我们输入的值替换它：

           {a + b
           for a in 'yz'
           for b in ['y','z']}

希望您能看到我们会得到['yy', 'yz', 'zy', 'zz']，我们会：

>>> perms = gen_perms(2,'yz')
>>> print len(perms)
4
>>> print sorted(perms)
['yy', 'yz', 'zy', 'zz']

在这里使用集合非常好，因为如果我们将文本更改为包含重复的字母，它们将被忽略：

>>> perms = gen_perms(2,'yyyzz')
>>> print len(perms)
4
>>> print sorted(perms)
['yy', 'yz', 'zy', 'zz']