Generate OPTIONAL/UNION permutations more efficiently

[patrickkwang]

Instead of nesting UNIONs (2^n total), it may be possible to flatten them and use a smaller set of permutations.

---

We have a set of n things. We need to generate a set of permutations such that each unique subset of length m<=n occurs as a prefix in at least one of these permutations. We'd like the set of permutations to be as small as possible.

There is just one solution for n=2: f_2(a, b) = [ab, ba]

The current scheme just uses this and recurses for n>2. So for example, f_3(a, b, c) becomes f_2(f_2(a, b), c) = [abc, bac, cab, cba].

However, n=3 could be solved more efficiently by, for example: [abc, bca, cab].

For n=4, the current scheme generates 8 sets, but we can make do with 6, for example: [abcd, bcda, cdab, dabc, ac**, bd**]

The size of these sets is (weakly?) lower-bounded by max(n choose m | m<=n). That bound is achievable for n<=4 (at least), as shown in the examples above.

We need an algorithm for generating efficient sets, for arbitrary n. If that doesn't pan out, we can just tabulate solutions for a range of low n and enforce an upper bound, e.g. n<=4.

[cbizon]

I'll think a bit more, but I suspect that come nested cyclic permutations will work. so for the 4 case you cycle
abcd
bcda
cdab
dabc

But to get some extra combos you need to now cycle the last 3 for the first two sequences, once each.

So for longer sequences there's probably a level of nesting for each additional length, and some number of sequences that you have to apply the nesting to?

[patrickkwang]

We might could make this a bit more complicated in practice because we can share computation between permutations with shared prefixes. For example, we only have to compute a once for abcd and acbd. I think this does not impact the way we generate these permutations until at least n=6, and maybe never... But it may be something to revisit later.