Алгоритм для всех перестановок строки в 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 = 'уг':

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

При п = 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']