Пусть последовательность из 0 и 1 длиной N такова, что в ней любая возможная подпоследовательность длины М встречается ровно один раз.
Вопросы:
1) Каковы алгоритмы генерации всех таких последовательностей?
2) Сколько различных последовательностей существует, без учёта циклических сдвигов и зеркальных отражений?
PS. Есть смутное (не доказанное точно) предположение, что ответы на эти вопросы могут оказаться не так уж просты, по крайней мере могут выходить за границы обычной арифметики
DjAndy.
M>Пусть последовательность из 0 и 1 длиной N такова, что в ней любая возможная подпоследовательность длины М встречается ровно один раз.
M>Вопросы: M>1) Каковы алгоритмы генерации всех таких последовательностей? M>2) Сколько различных последовательностей существует, без учёта циклических сдвигов и зеркальных отражений?
Где N=2^M+M-1, а последние М-1 символов цепочки, совпадают с первыми М-1 символами?
Правильно? Иначе, бессмысленно говорить о цеклических сдвигах.
Тогда, без нарушения общности, можно предположить что искомая последовательность начинаестя с М нулей.
Более того (M+1)й и (N-M)й символ — единици (иначе последовательность из М-нулей встречается дважды).
Остается (M+2^M-1)-(2M+1)=2^M-M-2 символов, которые надо подобрать.
Подозреваю, что для каждого М, существует единственая такая последовательнсть.
Во всяком случае для М=2,3,4 удалось найти только по одной последвательности.
Здравствуйте, Chorkov, Вы писали:
M>>Пусть последовательность из 0 и 1 длиной N такова, что в ней любая возможная подпоследовательность длины М встречается ровно один раз.
C>Где N=2^M+M-1, а последние М-1 символов цепочки, совпадают с первыми М-1 символами? C>Правильно? Иначе, бессмысленно говорить о цеклических сдвигах.
Совершенно верно! (Это я думал об одном, а писал другое, как всегда )
C>Тогда, без нарушения общности, можно предположить что искомая последовательность начинаестя с М нулей. C>Более того (M+1)й и (N-M)й символ — единици (иначе последовательность из М-нулей встречается дважды).
C>Остается (M+2^M-1)-(2M+1)=2^M-M-2 символов, которые надо подобрать.
C>Подозреваю, что для каждого М, существует единственая такая последовательнсть. C>Во всяком случае для М=2,3,4 удалось найти только по одной последвательности.
C>
Только похоже на шутку о физиках: "Гипотеза :Все числа меньше 100". Ставим экперимент: первые 99 чмсел меньше ста. Поскольку экпериментальных опровержений не выявлено, считаем гипотезу верной".
На самом деле, уже при М=5 мы имеем не менее двух последовательностей:
...
M>Только похоже на шутку о физиках: "Гипотеза :Все числа меньше 100". Ставим экперимент: первые 99 чмсел меньше ста. Поскольку экпериментальных опровержений не выявлено, считаем гипотезу верной".
Я физик по образованию ...
M>На самом деле, уже при М=5 мы имеем не менее двух последовательностей:
M>
...
M>>Только похоже на шутку о физиках: "Гипотеза :Все числа меньше 100". Ставим экперимент: первые 99 чмсел меньше ста. Поскольку экпериментальных опровержений не выявлено, считаем гипотезу верной". C>Я физик по образованию ...
& (если что — извиняюсь )
M>>На самом деле, уже при М=5 мы имеем не менее двух последовательностей:
M>>
M>Пусть последовательность из 0 и 1 длиной N такова, что в ней любая возможная подпоследовательность длины М встречается ровно один раз.
M>Вопросы: M>1) Каковы алгоритмы генерации всех таких последовательностей? M>2) Сколько различных последовательностей существует, без учёта циклических сдвигов и зеркальных отражений?
Ну вот, наконец написал нормальный (??) алгоритм генерации.
Результаты: (без циклических сдвигов)
M = 2, N = 4, count = 1 2^0
M = 3, N = 8, count = 2 2^1
M = 4, N = 16, count = 16 2^4
M = 5, N = 32, count = 2048 2^11
M = 6, N = 64, count = 67108864 2^26
Дальше считать не стал, уж очень большие цифры должны получиться.
