Generation
Duval (1988) provides an efficient algorithm for listing the Lyndon words of length at most n with a given alphabet size s in lexicographic order. If w is one of the words in the sequence, then the next word after w can be found by the following steps:
- Repeat the symbols from w to form a new word x of length exactly n, where the ith symbol of x is the same as the symbol at position (i mod length(w)) of w.
- As long as the final symbol of x is the last symbol in the sorted ordering of the alphabet, remove it, producing a shorter word.
- Replace the final remaining symbol of x by its successor in the sorted ordering of the alphabet.
The worst-case time to generate the successor of a word w by this procedure is O(n). However, if the words being generated are stored in an array of length n, and the construction of x from w is performed by adding symbols onto the end of w rather than by making a new copy of w, then the average time to generate the successor of w (assuming each word is equally likely) is constant. Therefore, the sequence of all Lyndon words of length at most n can be generated in time proportional to the length of the sequence. A constant fraction of the words in this sequence have length exactly n, so the same procedure can be used to efficiently generate words of length exactly n or words whose length divides n, by filtering out the generated words that do not fit these criteria.
Read more about this topic: Lyndon Word
Famous quotes containing the word generation:
“Most women of [the WW II] generation have but one image of good motherhood—the one their mothers embodied. . . . Anything done “for the sake of the children” justified, even ennobled the mother’s role. Motherhood was tantamount to martyrdom during that unique era when children were gods. Those who appeared to put their own needs first were castigated and shunned—the ultimate damnation for a gender trained to be wholly dependent on the acceptance and praise of others.”
—Melinda M. Marshall (20th century)
“A generation which has passed through the shop has absorbed standards and ambitions which are not of those of spaciousness, and cannot get away from them. Everything with them is done as though for sale, and they naturally have in view the greatest possible benefit, profit and that end of the stuff that will make the best show.”
—Alexander Herzen (1812–1870)
“One generation passeth away, and another generation cometh: but the earth abideth for ever. The sun also ariseth, and the sun goeth down, and hasteth to the place where he arose.”
—Bible: Hebrew Ecclesiastes 1:4,5.
Ernest Hemingway’s book title The Sun Also Rises (1926)