Рекурсивное решение в python. В этом коде хорошо то, что он экспортирует словарь с ключами в виде строк и всеми возможными перестановками в качестве значений. Все возможные длины строк включены, поэтому вы создаете надмножество.
Если вам требуются только окончательные перестановки, вы можете удалить другие ключи из словаря.
В этом коде словарь перестановок является глобальным.
В базовом случае я сохраняю значение как обе возможности в списке. perms['ab'] = ['ab','ba']
.
Для более длинных строк функция относится к более низким длинам строк и включает ранее вычисленные перестановки.
Функция выполняет две функции:
- вызывает себя с меньшей строкой
- возвращает список перестановок конкретной строки, если она уже доступна. При возврате к себе они будут использоваться для добавления к персонажу и создания новых перестановок.
Дорого на память.
perms = {}
def perm(input_string):
global perms
if input_string in perms:
return perms[input_string] # This will send a list of all permutations
elif len(input_string) == 2:
perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
return perms[input_string]
else:
perms[input_string] = []
for index in range(0, len(input_string)):
new_string = input_string[0:index] + input_string[index +1:]
perm(new_string)
for entries in perms[new_string]:
perms[input_string].append(input_string[index] + entries)
return perms[input_string]