# Sequence where every subset exists as some contiguous subsequence

Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of elements in a contiguous subsequence does not matter when they are considered as a set.

For example, such a minimal sequence for set $$\{1,2,3\}$$ is the sequence $$[1,2,3,1]$$. Here is the explanation.

• The set $$\{1,2,3\}$$ has 7 non-empty subsets: $$\{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,3\}, \{1,2,3\}.$$
• The sequence $$[1,2,3,1]$$ contains the following 7 contiguous subsequences
$$[1], [2], [3], [1,2], [2,3], [3,1], [1,2,3],$$ which correspond to the subsets respectively.
• On the other hand, a sequence of 3 numbers contains only 6 (non-empty) contiguous subsequences.
• Figure out the first few values and look if it appears in the OEIS. Aug 18 '21 at 4:32
• Wait, substring or subsequence? That's a big difference. Either way, as an upper bound we have the de Bruijn sequences, which are the shortest strings containing all substrings of length $n$ over some alphabet. Probably you can get shorter if you don't care about order like you do.
– orlp
Aug 18 '21 at 9:43
• Following the hint of @orlp, I googled "unordered De Bruijn" and our friends at math.SE had some first thoughts: de Bruijn sequence in which order of subsquences doesn't matter. Note that in a de Bruijn sequence there are supposed to be no repetitions, so that will be a stronger requirement than "shortest". Aug 18 '21 at 12:15
• Just adding here, an obvious lower bound for the length of such a string is $\frac{2^n}{n}$, as a set contains $2^n$ subsets but a string om some $m$ characters only contains about $nm$ substrings of length at most $n$. Achieving this lower bound implies that every subset is represented only once and no substring is a multiset, which still sounds pretty optimistic. Aug 18 '21 at 15:50
• You should explain that by subsequence, you mean a contiguous subsequence. Also, for a subsequence to match a set, it is allowed that symbols repeat in it. For example, 12231 is also a solution (albeit not a minimum length one). Is that on purpose? Aug 19 '21 at 1:17