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

[Corwin]

a(n) - самая короткая последовательность, которая содержит все подпоследовательности {1,...,n}. Если таких последовательностей несколько, то нужно выбрать (лексикографически) минимальную.

Например:
$a(3) = \{1,2,1,3,1,2,1\}$
содержит все перестановки {1,2,3}

Вот тут http://oeis.org/A136094 даны неправильные ответы для n > 4.

Я придумал некий алгоритм (интуитивно, без доказательства), но он для некоторых n даёт неверный результат (считал для всех n < 11).

Есть у кого-нибудь идеи, как решать, или хотя бы, что почитать на эту тему?


Предположительно, подобная задача была на одной из Всесоюзных Математических Олимпиад, поэтому запостил в этом разделе.

[gris]

Какая-то у Вас последовательность не такая. А где в ней $231$? Или я чего-то не понял?

+++ Ясно. То есть не обязательно непрерывным куском.

[Aritaborian]

Corwin, вы уверены, что OEIS содержит неверные данные? Источник-то авторитетный.

gris в сообщении #708723 писал(а):

А где в ней $231$? Или я чего-то не понял?

Как я понимаю идею ТС, чтобы получить $231$, нужно взять второй, четвёртый и пятый элементы $a(3) = \{1,2,1,3,1,2,1\}$

[Cash]

Aritaborian в сообщении #708787 писал(а):

Corwin, вы уверены, что OEIS содержит неверные данные? Источник-то авторитетный

Наверное, точнее - непроверенные.

Цитата:

The entries a(6) and a(7) should be checked! - N. J. A. Sloane, May 08 2009

Хотя, если у ТС есть результат получше - может поделитесь?

[Corwin]

$a(5) = \{1,2,3,4,5,1,2,3,4,1,5,2,3,1,4,2,3,5,1\}$
$a(6) = \{1,2,3,4,5,6,1,2,3,4,5,1,6,2,3,4,1,5,2,3,6,1,4,2,3,5,1,6\}$
$a(7) = \{1,2,3,4,5,6,7,1,2,3,4,5,6,1,7,2,3,4,5,1,6,2,7,3,4,1,5,2,6,3,7,1,4,2,3,5,1,6,7\}$

Как видите, мои варианты короче на 2, 3 и 4 цифры. Легко убедиться, что они содержат все перестановки.
Я на 95% уверен, что мои варианты являются кратчайшими по длине, но совсем не уверен, что они лексикографически минимальные.

a(10) = 1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,1,10,2,3,4,5,6,7,8,1,9,2,10,3,4,5,6,7,1,8,2,9,3,
        10,4,5,6,1,7,2,8,3,9,4,5,10,1,6,2,7,3,8,4,5,9,1,10,2,6,3,7,8,4,5,1,9,2,3,4,5,6,7,8,10,1

[Aritaborian]

Cash в сообщении #708859 писал(а):

Наверное, точнее - непроверенные.

Упс, я не посмотрел упомянутую страницу у Слоуна, просто наехал на ТС. Зря. Corwin, каюсь.

Corwin в сообщении #708687 писал(а):

Я придумал некий алгоритм

Можно алгоритм в студию?

[Cash]

Всё верно.
Если присмотреться к числам, указанным в OEIS, то с $a_5$ они построены по примитивному правилу, гарантирующему появление любой перестановки, но, скорее всего, далекому от оптимальности.
Сначала возрастаем от $1$ до $n$, потом убываем до $1$, затем снова возрастаем до $n$, опять убываем до $1$ - и таких вагонов всего $n$.
Что Corwin всем наглядно и продемонстрировал

[Corwin]

Цитата:

Можно алгоритм в студию?

А смысл? Он же неправильно считает.
Я нахожу число, которое содержит все подпоследовательности длины один. Затем добавляю цифры, которых не хватает для того, чтобы в нём содержались все подпоследовательности длины два. И так далее. То есть, жадный алгоритм - без перебора.
Добавив немного перебора, я нашёл меньшие числа (той же длины) для n = 6, 7, 8. А уже для n = 9 слишком долго считает - я не дождался ответа. Кроме того, так как перебор неполный, я по-прежнему не знаю, можно ли найти числа ещё меньше.

[maxal]

Я исправил A136094. Но на самом деле основной для этой задачи является последовательность A062714, дающая длины соответствующих последовательностей. С достоверностью они установлены только для $n\leq 5$, а для $n\geq 6$ приводятся следующие оценки сверху:
8, 39, 52, 67, 84, 103, 124, 147, 172, 199, 227, 258, 291 and 326

Верхние оценки 8 и 39 для $n=6,7$ подверждаются также последовательностями, приведенными Corwin.

A062714 приводит общую конструкцию, доказывающую оценку сверху на длину $(n-1)^2+3$ для $n>2$. Однако, $n=16$ есть пример длины 227, показывающий что эта оценка не является точным значением.

[Aritaborian]

maxal, я правильно понимаю, что нахождение точных решений возможно лишь брутфорсом, а это слишком трудоёмко?

[maxal]

Aritaborian, правильнее сказать, что ничего существенно лучше брутфорса пока не придумано. Иначе бы в A062714 было бы куда больше членов. Но это не означает, что более быстрого способа вычислений не существует.

-- Sun Apr 14, 2013 11:06:47 --

См. также задачу 187 в Сборнике задач-монстров по математике под ред. А. Я. Белова

[Corwin]

Corwin в сообщении #708885 писал(а):

Я на 95% уверен, что мои варианты являются кратчайшими по длине, но совсем не уверен, что они лексикографически минимальные.

95% не сработали :(.

То есть, мой алгоритм не даёт даже кратчайшую подпоследовательность. Например, для n=10:

123456789A1234567891A2345678192A3456718293A4561728394A51627384915A2637481952A3647189
123456789A1234567891A23456781923456A71892345617A89234516789234A1567892341A567892341

Первая последовательность - это то, что даёт мой алгоритм.
Вторая последовательность короче и тоже содержит все перестановки.

-- 15.04.2013, 15:53 --

maxal
Спасибо за информацию. Особенно за текст задачи.

[Corwin]

maxal в сообщении #710031 писал(а):

Я исправил A136094. Но на самом деле основной для этой задачи является последовательность A062714, дающая длины соответствующих последовательностей. С достоверностью они установлены только для $n\leq 5$, а для $n\geq 6$ приводятся следующие оценки сверху:
28, 39, 52, 67, 84, 103, 124, 147, 172, 199, 227, 258, 291 and 326

Для $n = 6$ длина $len = 28$
Для $n = 7$ длина $len = 39$
То есть, верхняя оценка совпадает с нижней оценкой. Это доказано тут (by Malcolm Newey):
http://infolab.stanford.edu/pub/cstr/reports/cs/tr/73/340/CS-TR-73-340.pdf

Для $n \geqslant 8$ существуют следующие оценки сверху:
52, 67, 83, 102, 123, 145, 170, 197, 225, 256, 289, 323

Формула выглядит так:
$len = n^2 - (7n - 19)/3$
Источник:
A Construction of Short Sequences Containing All Permutations of a Set as Subsequences (by Saša Radomirović)

[maxal]

Corwin, спасибо за информацию. Обновил A062714.

[Corwin]

Как быстро проверить список чисел (содержат ли они все перестановки)?