Sign in to follow this  
rldivide

De Bruijn sequence with no direct repetition ?

Recommended Posts

Hello,

I'm looking for an algorithm which would generate a De Bruijn-like sequence with no direct repetition : I mean that a letter should not be directly followed by the same letter.

In my project, I need to generate such a sequence with an alphabet of size k=3 and order n=5.

Is there such an algorithm ?

thanks !

Share this post


Link to post
Share on other sites
Generate a graph where each node contains each of the sequences of length 4. Create a directed edge from each node where each edge is labeled with the alphabet element that is not the last letter in the vertex data. Each edge would go to the node with the sequence formed by the last three letters of the node data concatenated with the edge letter. Ex: 1231 would have two outbound edges: 2 would go to 2312 and 3 would go to 2313. Generate an Eulerian path over the graph using Fleury's algorithm.

Share this post


Link to post
Share on other sites
Emergent: I'm not sure that would help, since I can see in your sequence some direct repetition (00 / 11 / 22 ) - unless I did not get your point.

no such user: This look interesting but I'm not sure I understand the whole graph process... Do you have something more visual to explain it ? Thanks

Share this post


Link to post
Share on other sites
Let's start with order n = 2 for a moment.

Vertex (Edge -> Destination Vertex)
1 (2 -> 2, 3 -> 3)
2 (1 -> 1, 3 -> 3)
3 (1 -> 1, 2 -> 2)

Start at an arbitrary node. Try to find a way to traverse the graph visiting each edge exactly once.
1 to 2 to 3 to 1 to 3 to 2 to 1

Concatenate the first vertex with the edges followed: 1231321 This sequence contains every possible subsequence of length 2 that does not have direct repetition.

Let's consider order n = 3 next.

Vertex (Edge -> Destination Vertex)
12 (1 -> 21, 3 -> 23)
13 (1 -> 31, 2 -> 32)
21 (2 -> 12, 3 -> 13)
23 (1 -> 31, 2 -> 32)
31 (2 -> 12, 3 -> 13)
32 (1 -> 21, 3 -> 23)

Try doing the same steps.

Share this post


Link to post
Share on other sites
Quote:
Original post by rldivide
Emergent: I'm not sure that would help, since I can see in your sequence some direct repetition (00 / 11 / 22 ) - unless I did not get your point.


Ah, no, I read your post way too fast and missed your point.

Gray codes -- what I described -- have the property that, between successive sequences, only one letter changes. That's not what you wanted.

Share this post


Link to post
Share on other sites
For a pseudo-random 3^5 sequence, something like this?
1 3 2 3 2 3 1 3 1 2 1 2 3 1 2 3 1 3 2 3 1 2 1 3 1 2 3 2 3 2 1 2 1 2 1 3 2 1 3 1 3 1 3 2 1 2 3 2
[1 3 2 3] (the last possible quintuplet being found wrapped around to the beginning of the sequence).

I haven't found a foolproof method to /rapidly/ generate such sequences, but they can be generated in a brute force manner by enumerating all possible subsequences, removing ones that contain consecutive repeats of any character, and then interleaving the ones that remain.

A random choice from all the possible subsequences:

1 3 2 3 2

pick without replacement from those that match:
3 2 3 2 3
3 2 3 2 1

to create:
1 3 2 3 2 (3)

pick without replacement from:
2 3 2 3 1
2 3 2 3 2

to create:
1 3 2 3 2 3 (1)

...and so on continuing to append the final character from a subsequence that begins the same way the last subsequence ends. The difficulty comes when picking this way because the algorithm will dead end when it finds no remaining subsequences that match. Towards the end of sequence computation, this happens far more often than not, so the algorithm must build a decision tree as it goes in order to enable labeling of dead ends and allow it to backtrack to pick a different route.

Ugly, I know. I am quite sure there's a more elegant way of going about it, but I haven't yet hit upon it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this