用于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