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.

    http://en.wikipedia.org/wiki/Lyndon_word

    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:

    http://www-igm.univ-mlv.fr/~berstel/Articles/1994AverageCostDuval.pdf

    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
    repeat:
    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
    end

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

    http://ehess.modelisationsavoirs.fr/marc/publi/softcomputing/5000387periodicity.pdf
     
    Last edited: Jul 31, 2012
  2. jcsd
  3. Jul 31, 2012 #2
    Here's my implementation:

    #include<iostream>
    #include<windows.h>

    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();
    duval(w);
    cout << "\nComputing time was " << (GetTickCount() - startime) << " milliseconds\n\n";
    cin.get();
    cin.get();
    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
    Nprim++;

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

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

    } while(i);
    cout << "\nNumber of Lyndon words is " << Nprim << endl;
    }
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook