# De Bruijn sequence with no direct repetition ?

## Recommended Posts

rldivide    132
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 on other sites
no such user    280
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 on other sites
Emergent    982
Are you familiar with the reflection algorithm for generating Gray codes? You can do the same sort of thing in n-ary:

012|V000102121110202122...etc.

##### Share on other sites
rldivide    132
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 on other sites
no such user    280

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 on other sites
Emergent    982
Quote:
 Original post by rldivideEmergent: 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.

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

##### Share on other sites
abulafia    100
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.