de Bruijn sequence in which order of subsquences doesn't matter

Question

A de Bruijn sequence of of size $k$ will contain every single subsequence of length $n$ exactly once within a single cycle. Is there another similar type of sequences in which the order of the subsequence elements is not considered?

For instance, consider this de Bruijn sequence of alphabet size 3 and subsequence length 3:

$0\ 0\ 0\ 1\ 0\ 0\ 2\ 0\ 1\ 1\ 0\ 1\ 2\ 0\ 2\ 1\ 0\ 2\ 2\ 1\ 1\ 1\ 2\ 1\ 2\ 2\ 2\ (0\ 0)$

In the case above, certain subsequences will have the same elements but in different order (e.g. $0\ 0\ 1$, $0\ 1\ 0$, $1\ 0\ 0$).

For the case above, I would like to find a sequence which would list all subsequences below exactly once before looping:

$0\ 0\ 0$

$0\ 0\ 1$

$0\ 0\ 2$

$0\ 1\ 1$

$0\ 1\ 2$

$0\ 2\ 2$

$1\ 1\ 1$

$1\ 1\ 2$

$1\ 2\ 2$

$2\ 2\ 2$

Does such a sequence exist?

Answer 1

For the purposes of this post, I will call unordered de Bruijn sequences the sequences satisfying the definition given in the question.

For any alphabet size $k$ and $n=1$, the sequence $1 \ 2 \ \ldots \ k$ is an unordered de Bruijn sequence.

For alphabet size $k=2$, such sequences exist only if $n=1$. Indeed, there are $n+1$ sequences of length $n$ on a two-letter alphabet (up to reordering), so an unordered de Bruijn sequence has to contain exaclty $n+1$ letters. However, it must contain $0\ 0 \ \ldots \ 0$ and $1\ 1 \ \ldots \ 1$ as subwords, so it must have at least $2n$ letters. Thus $n=1$.

In general, we can say this:

• An unordered de Bruijn sequence contains exactly $\binom{n+k-1}{k-1}$ letters, since this is the number of words of length $n$ in $k$ letters (up to reordering).

• In an unordered de Bruijn sequence, the number of occurences of a given letter is the same for all letters. In particular, $k$ divides $\binom{n+k-1}{k-1}$.

This last point rules out your example where $n=k=3$. In fact, for $k=3$, it rules out the cases where $n$ is divisible by $3$.

Beyond this, I don't know what can be said. I haven't seen an unordered de Bruijn sequence yet (except when $n=1$).

Answer 2

First, let's solve a simpler problem.

De Bruijn sequences involve a sliding window, which contains every possibility exactly once as it slides around the circular sequence.

But here we do not care about the order of elements within the window. So instead of a "window" that advances by removing the leftmost element and adding a rightmost element, let's instead consider a "bag" of $n$ unordered elements, that advances by removing any element and replacing it with a new one. We will say an unordered de Bruijn sequence is a sequence of bag-contents that cycles through all possibilities exactly once.

Examples:

De Bruijn Sequence                    Unordered De Bruijn Sequence
     000   window size n=3                       00   bag size n=2
     001   alphabet size k=2                     10   alphabet size k=3
     011                                         11
     111   at each step, first element is        12   at each step, exactly
     110   removed, others shift to left,        22   one element changes
     101   and new element is added to end       02
     010                                         00 = start
     100
     000 = start

Let's consider the question:
     Is there an unordered de Bruijn sequence for all positive $n$ and $k$?

The answer to this question is yes (when $n \ge 2$ or $k=1$), as we can see by looking at the graph of possible bag states, which is an $(n-1)$-dimensional triangular grid of size $k+1$. The question amounts to asking whether there is a Hamiltonian cycle through this grid.

The existence of a Hamiltonian cycle is easy to see inductively: an $(n-1)$-dimensional pyramid of size $k+1$ can be decomposed into a slightly smaller $(n-1)$-dimensional pyramid of size $k$, plus a face which is a $(n-2)$-dimensional pyramid of size $k+1$. Using (inductively) Hamiltonian cycles through both of these, we mark an edge of the pyramid's cycle where it leaves a corner of the pyramid as $A$, and a similar edge of the face's cycle where it leaves a corner of the face as $B$. Now we extend the pyramid by placing the face next to it so that $A$ and $B$ are parallel and adjacent. This way, we can connect the Hamiltonian cycles to each other, by replace $A$ and $B$ with two edges that connect the cycles into one Hamiltonian cycle of the original pyramid.

The base case for the induction has two parts:
• A pyramid of size 1 in any number of dimensions has just 1 point in it, and its trivial empty cycle works for the inductive step.
• A pyramid of dimension 2 always has a Hamiltonian cycle:

                                                     *
                                     *              / \
                       *            / \            / /__
           *          / \          / __\          / ____\     etc.
 *        . .        / /__        / /____        / /______
* *      * . *      *_____*      *_______*      *_________*

---

Now let's go back and consider the original question, which involved a sliding window. Now, we still need to find a Hamiltonian cycle through the pyramid, but now our moves are constrained by needing to always remove the element that was inserted $n$ steps ago.

When $k=1$, there is a cycle of length 1 regardless of $n$.

When $k=2$ (a one dimensional pyramid, i.e., a segment), there is a path but no cycle when $n>1$.

When $k=3$, there is a cycle for $n=1$ and $n=2$, and a Hamiltonian path (but no cycle) when $n=3$, and not even a path when $n>3$. To see this, note that when leaving a corner of the triangle, the path must go directly towards the opposite side. For the second corner visited by the path, the path must go all the way to the opposite side, for either direction of travel, which results in topological trouble for visiting the entirety of the triangle.

For $k \ge 4$, the topological trouble goes away, and when $n$ is large, the large number of possible Hamiltonian cycles may make up for the restriction coming from the sliding window, so I would guess there are such Hamiltonian cycles, but I haven't seen any examples yet.

Answer 3

When size of the alphabet (k) equals 1 and the length of the subsequences (n) is 1 there is a valid cycle, for higher n the additional repetitions from overlap invalidate the cycle (00"0" for instance has it's two 0's and then the loop adds a second instance of two 0's, in other words, it repeats.) When n is 0 you must have a valid cycle for any alphabet but this is trivial. When n=2 there is a valid cycle for k=3,5 (001122"0", 002113224330441"0") I have not found valid cycles for other k when n=2. I can confirm that if they exist they are of odd k.

When k is even each digit must touch an odd number of other digits, which is impossible since it must be a cycle, so each digit must touch 2 other digits, one on each side. there is the exception of the digit that touches itself, but those form pairs and do not solve the problem. I do not believe this holds for n other than 2, but it may, or it may hold on all even n.

While standard De Bruijn cycles are very simple to compute (for how complicated they are), but these are very difficult it seems. though that may just be because I have not yet found a method of doing so.