Вот быстрый алгоритм, который выдает короткую строку, содержащую все перестановки. Я почти уверен, что он даст кратчайший ответ, но у меня нет полного доказательства в руках.
Объяснение. Ниже приведено дерево всех перестановок. Картина неполная; представьте, что дерево вечно направо.
1 --+-- 12 --+-- 123 ...
| |
| +-- 231 ...
| |
| +-- 312 ...
|
+-- 21 --+-- 213 ...
|
+-- 132 ...
|
+-- 321 ...
Узлы на уровне k этого дерева - все перестановки длины
к . Кроме того, перестановки в определенном порядке с большим
перекрытия между каждой перестановкой и ее соседями сверху и снизу.
Если быть точным, первый дочерний узел каждого узла можно найти, просто добавив следующий
символ до конца. Например, первый ребенок 213 будет 2134. Остальные
детей можно найти, повернув к первому ребенку, чтобы оставить один символ в
время. Вращение 2134 даст 1342, 3421, 4213.
Взятие всех узлов на заданном уровне и связывание их вместе, перекрывая
максимально, выдает строки 1, 121, 123121321 и т. д.
Длина n -ой строки в этой последовательности равна сумма для x = от 1 до n из x! . (Вы можете доказать это, наблюдая, сколько не перекрывается между соседними перестановками. Братья и сестры перекрываются во всех символах, кроме 1; двоюродные братья перекрываются во всех символах, кроме 2; и т. Д.)
Набросок доказательства. Я не полностью доказал, что это лучшее решение, но вот набросок того, как будет проходить доказательство. Сначала покажите, что любая строка, содержащая n различных перестановок, имеет длину & ge; 2 n - 1. Затем покажите, что добавление любой строки, содержащей n + 1 различных перестановок, имеет длину 2 n + 1. То есть добавление еще одной перестановки приведет к стоить вам две цифры. Приступить к расчету минимальной длины строк, содержащих n P r и n P r + 1 отдельная перестановка, до n! . Короче говоря, эта последовательность оптимальна, потому что вы не можете сделать ее хуже где-то в надежде улучшить ее где-то еще. Это уже локально оптимально везде. Все ходы являются принудительными.
Алгоритм. Учитывая весь этот фон, алгоритм очень прост. Пройдите по этому дереву на нужную глубину и объедините все узлы на этой глубине.
К счастью, нам не нужно строить дерево в памяти.
def build(node, s):
"""String together all descendants of the given node at the target depth."""
d = len(node) # depth of this node. depth of "213" is 3.
n = len(s) # target depth
if d == n - 1:
return node + s[n - 1] + node # children of 213 join to make "2134213"
else:
c0 = node + s[d] # first child node
children = [c0[i:] + c0[:i] for i in range(d + 1)] # all child nodes
strings = [build(c, s) for c in children] # recurse to the desired depth
for j in range(1, d + 1):
strings[j] = strings[j][d:] # cut off overlap with previous sibling
return ''.join(strings) # join what's left
def stringContainingAllPermutationsOf(s):
return build(s[:1], s)
Производительность. Приведенный выше код уже намного быстрее, чем мое другое решение, и он выполняет много операций по вырезанию и вставке больших строк, которые можно оптимизировать. Алгоритм может быть запущен во времени и памяти пропорционально размеру вывода.