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