Задача о нахождении минимального домена, содержащего все заданные последовательности

[m1el]

Задачи оформмять в виде видео это какой-то здец.
Это неудобно по многим причинам, например «перечитывать» условие сложно, или к неоднозначности языка добавится неоднозначность произношения…

По поводу самой задачи — вот статья, которая отвечает на очень похожий вопрос: habrahabr.ru/post/187882/

[m1el]

Сама задача — если задача решена для строк/чисел длиной N, она решена для всех строк с меньшей длиной потому что все строки включают в себя строки меньшей длины.
Минимальная длина строки ответа будет 2^N + N — 1 потому что в строке должно быть как минимум 2^N подстрок длиной N.
2 — 01100. 3 — 1011100010. 4 — 0010111101001100001.
Это ответы с минимальной длиной, но, возможно, решение не уникальное.

[MiXei4]

Не уникальное. Хотя бы потому, что нули и единицы можно поменять местами, отобразить зеркально. Да и без этого решений несколько.

[m1el]

jsfiddle.net/FXMt3/1/ — жадный алгоритм нахождения строки в лоб.

[valemak]

Простите, не удержался от полного перебора 0:-)

От 18 и меньше вариантов не обнаружено, по всей видимости 19, — это потолок.

Возможно, кому-то пригодится для анализа.

От 68985 до 504455

68985₁₀ = 0010000110101111001₂
69465₁₀ = 0010000111101011001₂
79329₁₀ = 0010011010111100001₂
81249₁₀ = 0010011110101100001₂
82809₁₀ = 0010100001101111001₂
82905₁₀ = 0010100001111011001₂
85473₁₀ = 0010100110111100001₂
85857₁₀ = 0010100111101100001₂
90601₁₀ = 0010110000111101001₂
92065₁₀ = 0010110011110100001₂
92281₁₀ = 0010110100001111001₂
92641₁₀ = 0010110100111100001₂
96361₁₀ = 0010111100001101001₂
96673₁₀ = 0010111100110100001₂
96793₁₀ = 0010111101000011001₂
96865₁₀ = 0010111101001100001₂
99817₁₀ = 0011000010111101001₂
104353₁₀ = 0011001011110100001₂
106873₁₀ = 0011010000101111001₂
108001₁₀ = 0011010010111100001₂
110345₁₀ = 0011010111100001001₂
110369₁₀ = 0011010111100100001₂
113705₁₀ = 0011011110000101001₂
113825₁₀ = 0011011110010100001₂
123241₁₀ = 0011110000101101001₂
124321₁₀ = 0011110010110100001₂
125017₁₀ = 0011110100001011001₂
125281₁₀ = 0011110100101100001₂
125705₁₀ = 0011110101100001001₂
125729₁₀ = 0011110101100100001₂
125993₁₀ = 0011110110000101001₂
126113₁₀ = 0011110110010100001₂
199147₁₀ = 0110000100111101011₂
199291₁₀ = 0110000101001111011₂
199635₁₀ = 0110000101111010011₂
200523₁₀ = 0110000111101001011₂
205291₁₀ = 0110010000111101011₂
206971₁₀ = 0110010100001111011₂
208707₁₀ = 0110010111101000011₂
212235₁₀ = 0110011110100001011₂
213747₁₀ = 0110100001011110011₂
213963₁₀ = 0110100001111001011₂
216003₁₀ = 0110100101111000011₂
216843₁₀ = 0110100111100001011₂
220691₁₀ = 0110101111000010011₂
220739₁₀ = 0110101111001000011₂
227411₁₀ = 0110111100001010011₂
227651₁₀ = 0110111100101000011₂
246379₁₀ = 0111100001001101011₂
246427₁₀ = 0111100001010011011₂
246483₁₀ = 0111100001011010011₂
246603₁₀ = 0111100001101001011₂
247915₁₀ = 0111100100001101011₂
248347₁₀ = 0111100101000011011₂
248643₁₀ = 0111100101101000011₂
249099₁₀ = 0111100110100001011₂
250035₁₀ = 0111101000010110011₂
250059₁₀ = 0111101000011001011₂
250563₁₀ = 0111101001011000011₂
250635₁₀ = 0111101001100001011₂
251411₁₀ = 0111101011000010011₂
251459₁₀ = 0111101011001000011₂
251987₁₀ = 0111101100001010011₂
252227₁₀ = 0111101100101000011₂
330557₁₀ = 1010000101100111101₂
330701₁₀ = 1010000101111001101₂
330941₁₀ = 1010000110010111101₂
331237₁₀ = 1010000110111100101₂
331565₁₀ = 1010000111100101101₂
331621₁₀ = 1010000111101100101₂
339005₁₀ = 1010010110000111101₂
339725₁₀ = 1010010111100001101₂
340157₁₀ = 1010011000010111101₂
341893₁₀ = 1010011011110000101₂
343085₁₀ = 1010011110000101101₂
343429₁₀ = 1010011110110000101₂
352573₁₀ = 1010110000100111101₂
353341₁₀ = 1010110010000111101₂
358477₁₀ = 1010111100001001101₂
358669₁₀ = 1010111100100001101₂
361717₁₀ = 1011000010011110101₂
361789₁₀ = 1011000010100111101₂
362405₁₀ = 1011000011110100101₂
364789₁₀ = 1011001000011110101₂
365629₁₀ = 1011001010000111101₂
368261₁₀ = 1011001111010000101₂
369125₁₀ = 1011010000111100101₂
370565₁₀ = 1011010011110000101₂
385333₁₀ = 1011110000100110101₂
385357₁₀ = 1011110000101001101₂
385445₁₀ = 1011110000110100101₂
386101₁₀ = 1011110010000110101₂
386317₁₀ = 1011110010100001101₂
386693₁₀ = 1011110011010000101₂
387173₁₀ = 1011110100001100101₂
387461₁₀ = 1011110100110000101₂
461231₁₀ = 1110000100110101111₂
461423₁₀ = 1110000101001101111₂
461647₁₀ = 1110000101101001111₂
462127₁₀ = 1110000110100101111₂
467375₁₀ = 1110010000110101111₂
469103₁₀ = 1110010100001101111₂
470287₁₀ = 1110010110100001111₂
472111₁₀ = 1110011010000101111₂
475855₁₀ = 1110100001011001111₂
475951₁₀ = 1110100001100101111₂
477967₁₀ = 1110100101100001111₂
478255₁₀ = 1110100110000101111₂
481359₁₀ = 1110101100001001111₂
481551₁₀ = 1110101100100001111₂
483663₁₀ = 1110110000101001111₂
484623₁₀ = 1110110010100001111₂
492759₁₀ = 1111000010011010111₂
492855₁₀ = 1111000010100110111₂
492967₁₀ = 1111000010110100111₂
493207₁₀ = 1111000011010010111₂
495831₁₀ = 1111001000011010111₂
496695₁₀ = 1111001010000110111₂
497287₁₀ = 1111001011010000111₂
498199₁₀ = 1111001101000010111₂
500071₁₀ = 1111010000101100111₂
500119₁₀ = 1111010000110010111₂
501127₁₀ = 1111010010110000111₂
501271₁₀ = 1111010011000010111₂
502823₁₀ = 1111010110000100111₂
502919₁₀ = 1111010110010000111₂
503975₁₀ = 1111011000010100111₂
504455₁₀ = 1111011001010000111₂

Приведённые 128 вариантов — далеко не все.

Дополнительные случаи можно обнаружить, если
во-первых, развернуть каждую из строк на 180⁰;
во-вторых, все 0 заменить на 1 и наоборот;
в-третьих, можно сначала применить во-первых, а потом во-вторых.
После этих манипуляций будет много попадаться дубликатов из этих 128, но новых наборов там должно быть много.

[halyavin]

Это же боян. Где только этой задачи не было. Решается через эйлеров цикл. Вершины — последовательности длины N-1. Ребра — последовательности длины N. Из каждой вершины выходят два ребра (получающихся дописыванием к последовательности 0 или 1 справа) и входят два ребра (приписываем 0 или 1 слева). Нужно найти цикл, который проходит через все ребра. Это делается стандартным способом.

Более того, в данном случае есть алгоритм, который просто идет по наименьшему неиспользованному ребру во всех случаях за исключением N+O(1) ребер (каких именно уже не помню).

[andreymironov]

Вот черт, именно этл решение пришло в голову ночью :)

[ScratchBoom]

Это последовательность де Брёйна
xakep.ru/2015/06/05/opensesame