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

Question

我需要用C++或python编写一个函数来获取一个字符串并打印所有可以加密的选项。例如 - 争夺（“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，我们递归运行该函数，所以要在基体的情况下从上方对这个被返回line：

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