генерировать последовательность со всеми перестановками

Question

Как сгенерировать кратчайшую последовательность с содержит все возможные перестановки?

Пример: Для длины 2 ответ равен 121, поскольку этот список содержит 12 и 21, которые являются всеми возможными перестановками.

Для длины 3 ответ 123121321, потому что этот список содержит все возможные перестановки: 123, 231, 312, 121 (недействительные), 213, 132, 321.

Каждое число (в пределах данной перестановки) может произойти только один раз.

Answer 1

Этот жадный алгоритм производит довольно короткие минимальные последовательности.

UPDATE: Обратите внимание, что for n ≥ 6, this algorithm does not produce the shortest possible string!

• сделать коллекцию всех перестановок.
• Удалить первую перестановку из коллекции.
• a = первая перестановка.
• Найдите последовательность в коллекции, которая имеет наибольшее перекрытие с концом a. Если есть галстук, выберите последовательность сначала в лексикографическом порядке. Удалите выбранную последовательность из коллекции и добавьте неперекрывающуюся часть в конец a. Повторите этот шаг, пока коллекция не будет пуста.

Для правильной работы необходим любопытный шаг размыкания; нарушая галстук в случайном порядке, похоже, приводит к более длинным строкам.

Я проверил (написав гораздо более продолжительную, медленную программу), что ответ, данный этим алгоритмом для длины 4, 123412314231243121342132413214321, действительно самый короткий ответ. Однако для длины 6 он дает ответ длиной 873, который длиннее кратчайшего известного решения.

Алгоритм O (n!).

Реализация в 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, ..., который, как представляется, this integer sequence.

У меня есть подозрение, вы можете сделать лучше, чем O (п!).

Answer 2

• Создайте все перестановки.
• Пусть каждая перестановка представляет собой узел в графе .
• Теперь, для любых двух состояний добавить край со значением 1, если они разделяют n-1 цифр (для источника от конца, и целей от конца), два, если они разделяют n-2 цифры и скоро.
• Теперь, вы должны найти кратчайший путь, содержащий n вершины.

Answer 3

Вот быстрый алгоритм, который создает короткую строку, содержащую все перестановки. Я уверен, что он дает самый короткий ответ, но у меня нет полного доказательства в руке.

Объяснение. Ниже представлено дерево всех перестановок. Изображение неполное; представьте, что дерево продолжается вечно направо.

1 --+-- 12 --+-- 123 ... 
    |  | 
    |  +-- 231 ... 
    |  | 
    |  +-- 312 ... 
    | 
    +-- 21 --+-- 213 ... 
      | 
      +-- 132 ... 
      | 
      +-- 321 ... 

Узлы на уровне к этого дерева являются все перестановки длины к. Кроме того, перестановки находятся в определенном порядке с множеством перекрытия между каждой перестановкой и ее соседями сверху и снизу.

Чтобы быть точным, первый ребенок каждого узла находится путем простого добавления следующего символа в конец. Например, первый ребенок из 213 будет равен 2134. Остальные детей находятся путем поворота к первому ребенку на один символ в времени. Вращающийся 2134 будет производить 1342, 3421, 4213.

Принимая все узлы на заданном уровне и нанизывая их вместе, перекрывая как можно больше, производит строки 1, 121, 123121321 и т.д.

В длина n-я строка в этой последовательности - the sum for x=1 to n of x!. (Вы можете это доказать, наблюдая, сколько не перекрывается между соседними перестановками. Братья и сестры перекрываются во всех, кроме одного символа, первые кузены перекрываются во всех, кроме двух символов, и т. Д.)

Эскиз доказательства. Я не полностью доказал, что это лучшее решение, но вот пример того, как будет продолжаться доказательство. Во-первых, показывают, что любая строка, содержащая п различных перестановок имеет длину н - 1. Тогда показывают, что при добавлении любой строки, содержащей п +1 различных перестановок имеет длину 2 п + 1. То есть, добавив еще один перестановка будет стоить вам двух цифр. Продолжить путем вычисления минимальной длины строк, содержащих _п P г и _п Р г + 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) 

Производительность. Вышеупомянутый код уже намного быстрее моего другого решения, и он много режет и вставляет большие строки, которые вы можете оптимизировать. Алгоритм может быть выполнен для выполнения во времени и в памяти, пропорциональных размеру выхода.