# Enumerating set combinations in an order that maximises the number of previously unseen subsets

Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$.

There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$.

There are $462! \approx 1.419 × 10^{1032}$ possible ordering of those sets. All ordering are in $\Phi_0$.

For a given ordering, $\phi \in \Phi_0$, $x_i^\phi$ is the set placed at position $i$.

Initial $\Phi_0$ was defined, following ones are defined as

$$\Phi_i = \left\{\,\phi \in \Phi_{i-1} \mid \not\exists \phi^\prime \in \Phi_{i-1} , C\left(i,\phi^\prime\right) \gt C\left(i,\phi\right)\, \right\}$$

where $C\left(i,\phi\right)$ is number of subsets given by $x^\phi_i$ which have not already exist as a subset of previous $x^\phi$'s

$$C\left(i,\phi\right)=\left|2^{x^\phi_i} \setminus \bigcup_{\forall h<i}{2^{x^\phi_h}} \right|$$

I'm looking for ways to efficiently enumerate any one of the orderings that exists in $\Phi_{462}$.

Any suggestions, pointing towards relevant/potential useful algorithms or papers would be appreciated.

There are $\sum_{j=1}^4 \binom{11}{j} = 561$ smaller subsets, and each $x^\phi$ contains $\sum_{j=1}^4 \binom{5}{j} = 30$ of them.
If you put all $462$ $5$-element sets in a priority queue with priority corresponding to the number of subsets which haven't yet appeared, after each pop you have to check $30$ subsets to see whether they're appearing for the first time, and for each $k$-element subset that is appearing for the first time you have to update the priorities of $\binom{11}{5-k}$ sets. There's an easy upper bound on the number of updates of $25410$.
As a follow-up optimisation, once every smaller subset has been seen (which happens after you've removed the first 90 elements from the priority queue), you can just iterate through the rest. If your priority queue is e.g. a binary heap, this will save you a lot of $O(\lg n)$ pops.
• This get most of the way there. This is guaranteed to give an ordering where $C(i,\phi)$ is monotonicity decreasing (which is the main desirable feature), but not necessarily a member of $\Phi_{462}$. Consider the priority queue when selecting the $i$th set in the ordering, there can be multiple sets of the same priority. At least one of them will allow you to construct an ordering in $\Phi_{462}$, but not necessarily all of them. – Gareth A. Lloyd May 21 '15 at 12:25
• I misunderstood the details of $\Phi_i$. Perhaps the question would be clearer if it didn't mention $\Phi_i$ at all, but defined a "new subset count" vector for each $\phi$ and asked for a lexicographically maximum "new subset count" vector. – Peter Taylor May 21 '15 at 20:46