String of integers puzzle

Question

I apologize for not have the math background to put this question in a more formal way. I'm looking to create a string of 796 letters (or integers) with certain properties.

Basically, the string is a variation on a De Bruijn sequence B(12,4), except order and repetition within each n-length subsequence are disregarded. i.e. ABBB BABA BBBA are each equivalent to {AB}. In other words, the main property of the string involves looking at consecutive groups of 4 letters within the larger string (i.e. the 1st through 4th letters, the 2nd through 5th letters, the 3rd through 6th letters, etc) And then producing the set of letters that comprise each group (repetitions and order disregarded)

For example, in the string of 9 letters:

A B B A C E B C D

the first 4-letter groups is: ABBA, which is comprised of the set {AB} the second group is: BBAC, which is comprised of the set {ABC} the third group is: BACE, which is comprised of the set {ABCE} etc.

The goal is for every combination of 1-4 letters from a set of N letters to be represented by the 1-4-letter resultant sets of the 4-element groups once and only once in the original string.

For example, if there is a set of 5 letters {A, B, C, D, E} being used Then the possible 1-4 letter combinations are: A, B, C, D, E, AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE, ABCD, ABCE, ABDE, ACDE, BCDE

Here is a working example that uses a set of 5 letters {A, B, C, D, E}.

D D D D E C B B B B A E C C C C D A E E E E B D A A A A C B D D B

The 1st through 4th elements form the set: D The 2nd through 5th elements form the set: DE The 3rd through 6th elements form the set: CDE The 4th through 7th elements form the set: BCDE The 5th through 8th elements form the set: BCE The 6th through 9th elements form the set: BC The 7th through 10th elements form the set: B etc.

* I am hoping to find a working example of a string that uses 12 different letters (a total of 793 4-letter groups within a 796-letter string) starting (and if possible ending) with 4 of the same letter. *

Here is a working solution for 7 letters:

AAAABCDBEAAACDECFAAADBFBACEAGAADEFBAGACDFBGCCCCDGEAFAGCBEEECGFFBFEGGGGFDEEEEFCBBBBGDCFFFFDAGBEGDDDDBE

Answer 1

An interesting variation would be to close the sequence off to form a "necklace" or "circular word", so that (for example) taking the last two letters and affixing the first two letters would give a set not generated from any of the length-4 substrings. An example for the set {A,B,C,D,E} is:

AAAABCDDDDABEEEEDACCCCEDBBBBCE

Note that whereas your sequence for {A,B,C,D,E} has length 33, the circular sequence has length 30. If we simply tack on the first 3 letters:

AAAABCDDDDABEEEEDACCCCEDBBBBCEAAA

we get a sequence of your type of length 33.

Answer 2

You could, of course, use brute-force but simplify the search tree by pruning with a backtracking algorithm. However, it intrigues me to think of it in terms of a more elegant approach, like the necklace listed below. Here are some of my working ideas on it thus far...

Start by breaking down the requirements into succint grouping of requisite necessary sequences, and groupings of forbidden sequences.

Since your alphabet has the letters $S_{letters}=${$A,B,...,K,L$} in your specific case of 12 letters, then the string must contain the sets { {$A$}, {$B$}, ..., {$K$}, {$L$} }. Each of the sets must be represented by the string of four repetitions of the letters of the alphabet, therefore your sequence must contain

$e^4$ for $e\in S_{letters}$

Thus the lower bound for the size of the target string is $|S_{letters}|\times4 = 48$.

The sequence $x^4 y^4, x\in S, y\in S$ is forbidden as the substrings of $xxxxyyyy$ will lead to the set {xy} being replicated 3 times:

{x}, {xy}, {xy}, {xy}, {y}.

More strongly, you can also say that sequence $x^3 y^3, x\in S, y\in S$ is forbidden as the substrings of $xxxyyy$ will lead to the set {xy} also being replicated 3 times

{xy}, {xy}, {xy}

Even more strongly, it can be said that $x^3y^2$ is forbidden as is $x^2y^3$ as each leads to a duplicate set sequence {xy},{xy}.

Thus each of the 4-repeats $e_i^4$ must be surrounded by letters which are not duplicated even once, e.g. $e_a e_b e_i^4 e_x e_y$, where $e_i \notin ${$e_a, e_b, e_x, e_y$}

In response to a comment below, let me explain that if $e_a=e_i$ or if $e_y=e_i$, then the sequence $e_a e_b e_i^4 e_x e_y$ will contain duplictes:

• If $e_a = e_i$, then $e_i e_b e_i^4 e_x e_y$ leads to $e_i e_b e_i e_i ...$ and $...e_b e_i e_i e_i ...$, both of which belong to the set {$e_b e_i$}

• If $e_y = e_i$, then $e_a e_b e_i^4 e_x e_i$ leads to $...e_i e_i e_i e_x ...$ and $...e_i e_i e_x e_i ...$, both of which belong to the set {$e_i e_x$}

Also in the necessary set are the $\binom{12}{4} = 495$ ways to pick 4 out of the 12 letters of your alphabet. These could be strung together and overlap, but they must be included in the sequence.

Answer 3

This is something that doesn't solve your problem but may give you some idea.

Consider the 11 letter case and ask for each set of 4 distinct letters to appear exactly once. Put the letters on the circle. Look at every triple that is oriented counterclockwise. Now let $a$ and $b$ be the distances (along the circle counterclockwise) between the first and the second and the second and the third letters respectively. Suppose we have two triples that can be joined together into a quadruple with distances $a,b$ and $b,c$. We put an edge between them if first, $a+b+c<11$ and second, the number $d$ that complements the sum to 11 is the largest number in the set $\{a,b,c,d\}$ that does not repeat (we call such triple $\{a,b,c\}$ admissible). Also, write the corresponding quadruple on that edge. Then every set ABCD of four letters appears once on some edge (the only way to get it is to have the A,B,C,D arranged so that they go counterclockwise and then the side of the corresponding quadrangle that is the largest (as measured along the circle) non-repeating one should not be there, which determines the triples). Also the in-degree of each triple is equal to the out-degree. Thus, it remains to show that the graph is connected to get the cycle going over each edge once. The key is that if $a,b$ forms an admissible triple with anything at all, then it does so with 1. Thus we can go $a,b,1,1,a',b'$ to take care of the length switch and $a,b,1,a,b$ to take care of the position switch.

There are two drawbacks in this argument:

1) It doesn't allow to do subsets of smaller size immediately. This, I believe, can be fixed with some effort.

2) One can spend eternity looking at the set $(3,3,3,3)$ and deciding which $3$ here is exceptional (needless to say, my "largest non-repeating number" rule was there just to define a unique exceptional element in any set of four positive integers adding up to 11. Almost any other rule would work just as well). This is a real trouble that also tempts me to ask if it is a pure coincidence that you gave examples for 5 and 7 letters but conveniently skipped 6.