1
$\begingroup$

Suppose we are given $n$ variables $X_i, i=1,\dots,n$, each taking values from $\{0,1\}$, and a constant integer $k$ with $ 0\leq k \leq n$.

What are some efficient ways to enumerate all possible combinations of values of $X_i$'s subject to the constraint $\sum_{i=1}^n X_i = k$?

A naive way is to first enumerate one by one all possible combinations of values of $X_i$'s without the constraint $\sum_{i=1}^n X_i = k$, and for each combination, check if it satisfies $\sum_{i=1}^n X_i = k$ (if it does, keep it; if it doesn't, discard it).

That naive way may be inefficient. For example, when $k=1$, a more efficient way will be for each $i$, letting $X_i=1$ and $X_j =0, \forall j \neq i$.

So I wonder for general $k$, what are some efficient ways to do the above task?

$\endgroup$
  • 1
    $\begingroup$ Are you asking for an ${n}\choose{k}$-iterator? You can check out this source code of NChooseKIterator. $\endgroup$ – Pål GD Mar 28 '13 at 9:11
  • $\begingroup$ @PålGD: Thanks, and close (probably yet). Is there some source for description of the algorithm? I am not familiar with Java, but I will have to implement it in Matlab. $\endgroup$ – Tim Mar 28 '13 at 9:13
  • $\begingroup$ See also this stackoverflow question: n choose k implementation. $\endgroup$ – Pål GD Mar 28 '13 at 10:41
  • $\begingroup$ What does "efficient" mean here? Note that for $k=n/2$, we must enumerate exponentially many (in $n$) items. $\endgroup$ – Raphael Mar 28 '13 at 10:44
  • 1
    $\begingroup$ Efficiency is not big-oh, but compact ways of computing the next item. So, elegant iterators. With combinatorial explosions that can save quite some (real) time. Knuth's Volume 4 has extensive info on generating partitions, combinations, and partitions, so it is not a what-ever implementation question. (end of proof by authority) $\endgroup$ – Hendrik Jan Mar 28 '13 at 11:10
4
$\begingroup$

First, separate the set of variables $I = \{1,\dots,n\}$ according to their values:

$\qquad\begin{align} I_+ &= \{ i \mid X_i = 1\} \text{ and} \\ I_- &= \{ i \mid X_i = 0\} \;. \end{align}$

Let $n_+ = |I_+|$ and $n_- = |I_-|$.

Given $X_1, \dots, X_n$ and $k$, it is clear that we have to choose $k$ indices from $I_+$ and arbitrarily many from $I_-$. That means we will have to output

$\qquad \binom{n_+}{k} \cdot 2^{n_-}$

solutions. Note that if we assume $\binom{a}{b} = 0$ for $b<0$ and $b>a$, this extends nicely to inputs that allow no solution.

Generating all valid solutions in a list can be done by two nested recursions: the outer creates all $k$-subsets of $I_+$, the inner all subsets of $I_-$. This way, no illegal solutions are investigated, which is as efficient as you can expect (up to list operations).

  outer(I+, 0, I-) = inner(I-)
| outer(I+, k, I-) =
    result = []
    foreach ( i in I+ ) {
      suffices = outer(I+ - i, k-1, I-)
      result ++= (suffices map { [i] ++ _ })
    }
    return result

  inner([])      = []
  inner(x::rest) = 
    smaller = inner(rest);
    return smaller ++ (smaller map { [x] ++ _ })

If you want an iterator, note that you can replace recursion with stacks (which allows you to compute it step by step) and emit solutions in the innermost call of inner. Of course, you'll have to reverse the way solutions are constructed (while descending, as opposed to during ascension as I did above).

$\endgroup$

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.