0
$\begingroup$

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.

$\endgroup$
1
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gareth A. Lloyd May 21 '15 at 12:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor May 21 '15 at 20:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.