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:
“In all our efforts to provide “advantages” we have actually produced the busiest, most competitive, highly pressured and over-organized generation of youngsters in our history—and possibly the unhappiest. We seem hell-bent on eliminating much of childhood.”
—Eda Le Shan (b. 1922)
“What makes this Generation of Vermin so very Prolifick, is the indefatigable Diligence with which they apply themselves to their Business. A Man does not undergo more watchings and fatigues in a Campaign, than in the Course of a vicious Amour. As it is said of some Men, that they make their Business their Pleasure, these Sons of Darkness may be said to make their Pleasure their Business. They might conquer their corrupt Inclinations with half the Pains they are at in gratifying them.”
—Joseph Addison (1672–1719)
“Against my will, I became a witness to the most terrible defeat of reason and to the most savage triumph of brutality ever chronicled ... never before did a generation suffer such a moral setback after it had attained such intellectual heights.”
—Stefan Zweig (18811942)