генерируйте последовательность со всеми перестановками
То, как я могу генерировать самую короткую последовательность с, содержит все возможные перестановки?
Пример: Для длины 2 ответ равняется 121, потому что этот список содержит 12 и 21, которые являются всеми возможными перестановками.
Для длины 3 ответ 123121321, потому что этот список содержит все возможные перестановки: 123, 231, 312, 121 (недопустимый), 213, 132, 321.
Каждое число (в рамках данной перестановки) может только произойти однажды.
3 ответа
Этот жадный алгоритм производит довольно короткие минимальные последовательности.
UPDATE: Обратите внимание, что для n ≥ 6, этот алгоритм не производит самую короткую возможную строку!
- Создайте коллекцию всех перестановок.
- Удалите первую перестановку из коллекции.
- Пусть a = первая перестановка.
- Найдите в коллекции последовательность, которая имеет наибольшее перекрытие с концом a. Если есть равенство, выберите последовательность, стоящую первой в лексикографическом порядке. Удалите выбранную последовательность из коллекции и добавьте не перекрывающуюся часть к концу a. Повторяйте этот шаг до тех пор, пока коллекция не станет пустой.
Любопытный шаг с разрывом ничьей необходим для корректности; разрыв ничьей случайным образом вместо этого, похоже, приводит к более длинным строкам.
Я проверил (написав гораздо более длинную и медленную программу), что ответ, который этот алгоритм выдает для длины 4, 123412314231243121342132413214321, действительно является самым коротким ответом. Однако для длины 6 он выдает ответ длиной 873, что длиннее, чем самое короткое известное решение.
Алгоритм имеет скорость O(n! 2).
Реализация на Python:
import itertools
def costToAdd(a, b):
for i in range(1, len(b)):
if a.endswith(b[:-i]):
return i
return len(b)
def stringContainingAllPermutationsOf(s):
perms = set(''.join(tpl) for tpl in itertools.permutations(s))
perms.remove(s)
a = s
while perms:
cost, next = min((costToAdd(a, x), x) for x in perms)
perms.remove(next)
a += next[-cost:]
return a
Длина строк, сгенерированных этой функцией, равна 1, 3, 9, 33, 153, 873, 5913, ... что представляется данной целочисленной последовательностью.
У меня есть подозрение, что вы можете сделать лучше, чем O(n! 2).
- Создание всех перестановок.
- Пусть каждая перестановка представляет узел в графе .
- Теперь для любых двух состояний добавьте ребро
со значением 1, если они разделяют
n-1цифр (для источника из конец, а для цели с конца ) два, если они разделяютn-2цифр и так далее. - Теперь вам осталось найти
кратчайший путь, содержащий
nвершин.
Вот быстрый алгоритм, который создает короткую строку, содержащую все перестановки. Я почти уверен, что он дает самый короткий ответ, но у меня нет полного доказательства.
Объяснение. Ниже представлено дерево всех перестановок. Картина неполная; представьте, что дерево всегда уходит вправо.
1 --+-- 12 --+-- 123 ...
| |
| +-- 231 ...
| |
| +-- 312 ...
|
+-- 21 --+-- 213 ...
|
+-- 132 ...
|
+-- 321 ...
Все узлы на уровне k этого дерева представляют собой перестановки длины k . Кроме того, перестановки расположены в определенном порядке с большим перекрытием между каждой перестановкой и ее соседями сверху и снизу.
Чтобы быть точным, первый дочерний узел каждого узла находится просто добавлением следующего символа в конец. Например, первым дочерним элементом 213 будет 2134. Остальные дочерние элементы будут найдены путем поворота к первому дочернему элементу, который оставит один символ за раз . Вращение 2134 даст 1342, 3421, 4213.
Если взять все узлы на заданном уровне и связать их вместе, максимально перекрывая , получатся строки 1, 121, 123121321 и т. Д.
] Длина n -й строки в этой последовательности равна сумме от x = 1 до n из x! . (Вы можете доказать это, наблюдая, насколько неперекрывается между соседними перестановками. Братья и сестры перекрываются во всех символах, кроме одного; двоюродные братья перекрываются во всех символах, кроме двух и т. Д.)
Набросок доказательства. Я не полностью доказал, что это лучшее решение, но вот набросок того, как будет проходить доказательство.Сначала покажите, что любая строка, содержащая n различных перестановок, имеет длину ≥ 2 n - 1. Затем покажите, что добавление любой строки, содержащей n +1 различных перестановок, имеет длину 2 n +1. То есть добавление еще одной перестановки будет стоить вам двух цифр. Выполните вычисление минимальной длины строк, содержащих n P r и n P r + 1 различных перестановок, вплоть до п! . Короче говоря, эта последовательность оптимальна, потому что вы не можете сделать ее хуже где-то в надежде улучшить ее где-то еще. Это уже везде локально оптимально. Все ходы форсированные.
Алгоритм. Учитывая всю эту предысторию, алгоритм очень прост. Обойдите это дерево до желаемой глубины и соедините вместе все узлы на этой глубине.
К счастью, нам не нужно строить дерево в памяти.
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)
Производительность. Приведенный выше код уже работает намного быстрее, чем другое мое решение, и он выполняет много операций по вырезанию и вставке больших строк, которые вы можете оптимизировать. Алгоритм можно заставить работать по времени и памяти пропорционально размеру вывода.