Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Lyndon words: Duval's algorithm and its time complexity

  1. Jul 31, 2012 #1
    Hi everyone,

    Duval' algorithm computes all the k-ary Lyndon words up to any length, say n. See here for a brief introduction to Lyndon words and note the section Generation.


    The article claims that
    "the sequence of all Lyndon words of length at most n can be generated in time proportional to the length of the sequence" and cites this paper:


    Now, I have implemented Duval's algorithm for the binary case (see below) in C++ and noted that the computation time increases by a factor of almost 2 whenever the length of the sequence increases by 1. This starts becoming especially noticeable by about length 25. This I think would seem to suggest that the time complexity is actually exponential, which contradicts the claim of the linear complexity of the algorithm. As I'm not an expert in C++, I'm wondering if I'm implementing this incorrectly, or inefficiently. What do you think? Here's the algorithm.

    In the binary case, i.e., k=2, Duval's algorithm simplifies to the following.

    w[1] ← 0
    i ← 1
    for j = 1 to n–i do
    w[i+j] ← w[j]
    /* at this point, w[1...i] is a Lyndon word */
    i ← n
    while i > 0 and w = 1
    do i ← i–1
    if i > 0 then w ← 1
    until i = 0

    You may find the algorithm in page 2 of this link as well:

    Last edited: Jul 31, 2012
  2. jcsd
  3. Jul 31, 2012 #2
    Here's my implementation:


    using namespace std;
    int m;

    void duval(bool w[]);

    int main() {
    cout << "Enter length of Lyndon word: ";
    cin >> m;

    bool *w = new bool[m+1];
    DWORD startime = GetTickCount();
    cout << "\nComputing time was " << (GetTickCount() - startime) << " milliseconds\n\n";
    delete[] w;
    return 0;

    void duval(bool w[]) {
    w[0] = 0;
    w[1] = 0;

    unsigned _int64 Nprim = 0;
    int i=1;

    do {

    for(int j = 1; j <= m-i; j++) {
    w[i+j] = w[j];

    // At this point, w[1...i] is a Lyndon word

    if(i == m) { // a Lyndon word of length m was found

    for(int k=1; k <=m; k++) {
    cout << w[k]; // print it
    cout << endl;

    i = m;
    while(i && w) {
    if(i) {
    w = 1;

    } while(i);
    cout << "\nNumber of Lyndon words is " << Nprim << endl;
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook