De Bruijn sequence in constant amortized time

Follow up on the previous blogpost.

Yesterday I wrote an algorithm in Java to generate de Bruijn sequences. But I had a breakthrough after reading:

K. Cattell, F. Ruskey, J. Sawada, M. Serra, C.R. Miers, Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2)

It has an algorithm which generates Lyndon words in CAT. CAT stands for Constant Amortized Time. This means that it isn’t really constant time, but approaches it very much. Calculating the worst-case scenario isn’t worth it. For example using an ArrayList in Java. The time to do insertions is said to be O(1), and this is true…. until the array underneath needs to be resized. During this resize it’ll take some more time. So the algorithm isn’t really constant time, but constant amortized time.

This is the program I ended up with. It is very very small. One of my most beautiful pieces of code. And it even supports non-binary alphabets (use the k-parameter).

public String generateDeBruijnSequence(int k, int n) {
	StringBuilder sequence = new StringBuilder();
	generateLyndonWords(1, 1, k, new int[n+1], sequence);
	return sequence.toString();
}

private void generateLyndonWords(int t, int p, int k, int[] a, StringBuilder sequence) {
	if (t > a.length-1) {
		if((a.length-1)%p==0) {
			for(int i = 1; i < p+1;i++) {
				sequence.append(a[i]);
			}
		}
	} else {
		a[t] = a[t-p]; 
		generateLyndonWords(t+1,p, k, a, sequence);
		for(int j=a[t-p]+1; j<=k-1; j++) {
			a[t] = j; 
			generateLyndonWords(t+1,t, k, a, sequence);
		}
	}
}

Update June 7th 2012:
I just stumbled across this interesting read: http://www.learner.org/courses/mathilluminated/units/2/textbook/07.php

The keypad example from that link can be easily calculated with the code above:
generateDeBruijnSequence(9, 5).length() = 59049 :-)