4
$\begingroup$

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.
$\endgroup$
11
  • 1
    $\begingroup$ Figure out the first few values and look if it appears in the OEIS. $\endgroup$ Aug 18 at 4:32
  • 2
    $\begingroup$ 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. $\endgroup$
    – orlp
    Aug 18 at 9:43
  • 2
    $\begingroup$ 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". $\endgroup$ Aug 18 at 12:15
  • 3
    $\begingroup$ 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. $\endgroup$
    – Highheath
    Aug 18 at 15:50
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 19 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.