редица на de Bruijn

В комбинаторната математика редица на de Bruijn (de Bruijn Sequence) e циклична последователност от ред n от азбука А, в която стринг с всякаква възможна дължина се появява точно веднъж като подстринг (subsring), като съседна последователност. Редиците носят името на холандския математик Nicolaas Govert de Bruijn. Стойностите са представени в http://oeis.org/A006480 с формулата: S(3,n): (3n)!/(n!)^3.

Пример: трябва да се представят всички числа от интервала 0-31 в двоичен код с възможно най-краткия запис. Всяко от числата е записано с 5 знака в двоичен вид и няма интервал между тях. Има няколко възможни решения и едно от тях е: 00000100011001010011101011011111. Стрингът трябва да се разглежда като пръстен: 000001000110010100111010110111110000 и подреждането е 00000:(0); 00001:(1); 00010:(2); 00100:(4); 01000:(8); 10001:(17); 00011:(3); 00110:(6); 01100:(12); 11001:(25); 10010:(18); 00101:(5); 01010:(10); 10100:(20); 01001:(9); 10011:(19); 00111:(7); 01110:(14); 11101:(29); 11010:(26); 10101:(21); 01011:(11); 10110:(22); 01101:(13); 11011:(27); 10111:(23); 01111:(15); 11111:(31); 11110:(30); 11100:(28); 11000:(24); 10000:(16). В скобите вдясно е записано съответното число в 10-чна бройна система. Отделните елементи могат да се конструират и като път в граф.

Съставете програма, чрез която се въвежда естествено число N от интервала [1..15] и се извеждат съответния брой последователни стойности от редица на de Bruijn. Програмата да използва две аналогични функции - рекурсия и итерация.

Подробно описание за редица на de Bruijn може да намерите на следните адреси: https://en.wikipedia.org/wiki/De_Bruijn_sequence, http://mathworld.wolfram.com/deBruijnSequence.html.

Разгледайте други основни типове примери и задачи свързани с изчисляване на факториел и работа с числови редици. Прочетете допълнителен материал за: праймориел, числа на Kummer, числа на Евклид, тороид на de Bruijn.