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:
“But it is fit that the Past should be dark; though the darkness is not so much a quality of the past as of tradition. It is not a distance of time, but a distance of relation, which makes thus dusky its memorials. What is near to the heart of this generation is fair and bright still. Greece lies outspread fair and sunshiny in floods of light, for there is the sun and daylight in her literature and art. Homer does not allow us to forget that the sun shone,—nor Phidias, nor the Parthenon.”
—Henry David Thoreau (1817–1862)
“We may consider each generation as a distinct nation, with a right, by the will of its majority, to bind themselves, but none to bind the succeeding generation, more than the inhabitants of another country.”
—Thomas Jefferson (1743–1826)
“The greater part of our best years has been passed for our generation in these two great worldconvulsions. All will be changed after this war, which spends in one month more than nations earned before in years ... there is no more security in our time than in those of the Reformation or the fall of Rome.”
—Stefan Zweig (18811942)