Алгоритм для всех перестановок строки в C ++ или Python

Question

Алгоритм для всех перестановок строки в C ++ или Python

Мне нужно написать функцию на C ++ или Python, которая получает строку и печатает все параметры, которые можно зашифровать. например — scramble («abc») напечатает —

abc
acb
bac
bca
cab
cba

Конечно, не только слова, длина которых равна 3.

0

c++function python recursion scramble

Решение

Другие решения

Вот более короткая рекурсивная функция для поиска всех перестановок букв в строке:

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

Когда 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']

1

Источник

Accepted Answer

В 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

6