2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 фраза без повторов слов
Сообщение11.10.2013, 15:50 
Аватара пользователя
Пусть имеется алфавит, состоящий из $L$ букв. Любую последовательность из $W$ букв назовем словом. Последовательность из $S\geq W$ букв назовем фразой. Какова максимальная длина фразы, все слова которой различны? (слова в фразе перекрываются, то есть фраза из $S$ букв содержит $S-W+1$ слов)


Например, $ L=2$(буквы А и Б), $W=3$ (возможные варианты слов ААА, ААБ, АБА, АББ, БАА, БАБ, ББА, БББ). Максимальная фраза без повторов содержит 10 букв. Примером такой фразы будет АААБАБББАА.

А можно ли решить в общем виде для произвольных $L$, $W$ и предложить алгоритм построения фразы максимальной длины?

 
 
 
 Re: фраза без повторов слов
Сообщение11.10.2013, 16:24 
Аватара пользователя
Собственно, $L^W + (W - 1)$, т.е. содержит все слова.
Это называется последовательности де Брёйна (de Bruijn). В статье http://en.wikipedia.org/wiki/De_Bruijn_sequence есть описание алгоритма (строится орграф, вершинами которого являются слова длины $W - 1$, а дугами соединены префикс и суффикс каждого слова длины $W$. Эйлеров цикл в таком графе будет соответствовать требуемой последовательности.)

 
 
 
 Re: фраза без повторов слов
Сообщение11.10.2013, 17:45 
Аватара пользователя
спасибо

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group