So, I was talking with Weregoose today about De Bruijn sequences, and I was intrigued (I think he was doing something for Sonlen or something, I don't know. I guess I did a bunch of work and saved 10 bytes in a program ). He had a list of bit strings, and he wanted to find the De Bruijn sequence representing them. I decided it might be fun to make a program that does just that, so I did. I think it's pretty neat. You pass it in a bunch of strings, and it finds the sequence for them. It generalizes glyphs, so it doesn't have to be ones and zeros, it can be anything. Here's the results for what he needed:

And here's the same thing using percent signs and greater-than signs:

It also doesn't need to be just two characters, you can do it with three or four etc. Here it is with zeros, ones, and twos:

Right now it needs that you have basically every string of length n on the alphabet a of size sigma to work, but I plan on making it try to fill in gaps if it can't get a sequence that works. It implies the length of each string based on the first one, so if your first string is five characters, all the rest need to be, too. It adds glyphs as it finds them, so you don't need to specify which glyphs to use, just input it as you see fit. It also generates the graph and outputs it so you can check it out:

I'd like to make it so that it actually draws the graph, too, at some point.

Download it at: http://merthsoft.com/SequenceFinder.zip. Note that it's pretty buggy, and I don't do any error checking, so it will crash if you don't put stuff in just right.

Ternary is fun! Also, I love making programs draw graphs of stuff; for some reason PHP is my language of choice for that because GD2 is quite powerful. Thanks for sharing this, Merth; nice work.

Wow that actually looks interesting. When you were talking about it in HC:WP it just confused me. lol

You and me both. I always far prefer (in terms of being able to understand it) the applied, implementation side of what we do rather than the theoretical, mathy side.

I like the applied side more, too, but I still have a soft-spot for the useless Denison focused on the theoretical over the applied, so I'm trained as a scientist, and self-taught as an engineer, more or less. That being said, I love graph theory and combinatorics, so this was right up my alley. If you guys have any specific questions, I'd be happy to answer them or defer them to Weregoose.

This is still sort of an applied question, but can you think of any practical applications for the De Bruijn sequence?

This is one where I'll have to defer to Weregoose for specifics, but I know he uses them for optimizations in his programs (or at least in the FFME program).

Sounds good. Is it just me, or do those examples resemble a certain kind of counting that I learned in Digital Logic Design that is currently completely escaping me?

For the most part I'm just counting up, but skipping a few in the first and second screen shots. You can, of course, put them in any order.

Interesting. I look forward to Weregoose's further clarifications of the implications.

http://video.google.de/videoplay?docid=6267783675810924557

Well, that was funny, but I still fail to see how it's actually helpful...

The only use that I've made habit is string-packing as a form of LUT:

Code:
(http://www.nickciske.com/tools/binary.php)

Notice how I can rotate both strings...

Code:


...and then drop the trailing, unused portion:

Code:


What's more, the "00000" can be cut down in order to combine the "XP" and "AB" without afflicting adjacent terms. (This creates a "necklace" which beats out the de Bruijn sequence for this set of words.) Therefore, de Bruijn is not always to be desired. But for its properties, it has been used for producing card tricks, for accurately measuring rotations on robots' wheels, for inventing a new kind of pseudo-random number generator, and for encoding everything from chessboard configurations to DNA. There are sources aplenty, and they all seem to reflect each other.

Well, there you go. That's pretty sweet. Thanks for explaining that, Weregoose!

*bump*
I started working on making it give a correct answer no matter what, so right now it's at the point where when I give it 000 001 it gives me 01011100(01), and it's adding a single node to get that. That's obviously not actually the shortest one, though. It can add lots of nodes, too. When I give is 000 001 002 it gives me 012221211120022011010202100(01) after adding 8 nodes. So it adds nodes, but it's still not so good at this "shortest" thing. Obviously 000001002 is shorter than 012221211120022011010202100(01) I guess I should have it check just concatenating them. But there's more to it than just concatenating them, because 0001 is a vlid answer to 000 001. So I'm not sure what kind of algo I should be using. Right now all it does is adds nodes systematically until if finds a path. For bigger lists that only need one or two more nodes, this is a fine solution, but obviously for the shorter ones, or things that need lots of nodes, this is slow and imperfect. Here's a screenshot:

The number at the bottom is the number of nodes it added to get to the string. You can download it at
http://merthsoft.com/SequenceFinder.zip
if you want to try it out!

This is great, glad to hear you didn't abandon development. I still don't personally have much reason to use it, but I admire your work.

I don't have much reason to use it, either.

Then all the more respect that you persevere anyway.

Your program is already doing what its name implies – a word that doesn't contain all words of a given length/alphabet is no longer de Bruijn. For that, IMO, a title change is in order. (A de Bruijn sequence would just be a special result of a more general method with the proper range of inputs, anyway.)

Here are four strings: 01011, 10001, 10100, and 11110. Build a directed graph attaching each string constantly on the right side in every way possible, all while labeling each branch with the amount of overlap. The shortest sequence is then made up of the path that maximizes the sum. (The root node has been duplicated onto the tip of each branch in order to consider rotations and, equivalently, leftward concatenation.)


Code:

01011110100(01) more tightly packs 01011, 10001, 10100, and 11110 than any other sequence.

Oh, how clever. I'll have to implement that. I guess I'll have three sequence finders, one that does what it currently does, one that adds all possible permutations and finds the sequence, and one which does that algorithm. Thanks, Weregoose!