2
$\begingroup$

Say there is a set of m·N named elements. How to produce all the (unordered) combinations of N-sized subsets?

For example, m=2 and N=2, the elements are called A, B, C and D. There will be 3 combinations: AB+CD, AC+BD and AD+BC.

For m=2 and N=3 there will be 10 combinations. In general, it will be:

$$\frac{(mN)!}{(N!)^m\cdot m!}$$

(thanks to Ross Millikan)

How to approach creating an algorithm that produces / iterates over the whole set of combinations?

$\endgroup$
0
1
$\begingroup$

Here is a program in Java that prints all unordered unique m-combinations of N-sized subsets of numbers from 0 inclusive to m * N exclusive. Click the run button to see some result.


The algorithm used in the program is adapted from the usual algorithm that produces all unique $k$-combinations out of $U$ objects. Here is some explanation of the recursive method, static void printCombinations(int m, final int N, int startNumber, boolean[] used, int[][] subsetsHolder, int curSubset, int toFill).

That method prints all print all unordered partition of numbers starting from 0 inclusive to m * N exclusive into m subsets of size N, where

  • the first curSubset subsets have been specified by subsetsHolder[0:curSubset] and
  • the first N - toFill numbers in the current subset, subsetsHolder[curSubset] have been specified in subsetsHolder[curSubset][0:N - toFill] and
  • if toFill is not N, all unspecified numbers in subsetsHolder[curSubset] must be at least startNumber. If it is N, the first number in subsetsHolder[curSubset] must be the first unused number.

The parameter used records those specified numbers. Namely, used[i] is true iff i has been specified somewhere. It is a convenience argument to ease the coding.


The body of that method is, in fact, quite simple, thanks to the power of recursion.

It first checks if all N numbers of the current subset is waiting to be selected.

  • If yes, there are two cases.
    • If curSubset is m, we have arrive at a full combination. Print and return.
    • Else we will find the smallest unused number. It becomes the 0-th element of the current subset, i.e., subsetsHolder[curSubset][0]. Recurse to fill the next number in the current subset.
  • Otherwise,
    • If there is no more to fill the current subset, recurse to fill the next subset.
    • Else let the next smallest number in the current subset to iterate through all numbers starting at startNumber. Recurse to fill the next number in the current subset.

It is not hard to prove that the algorithm/program prints all wanted combinations once in the natural lexicographic order.

$\endgroup$
1
2
$\begingroup$

Knuth wrote a chapter on this, as part of the new volume 4 of his Art of Computer Programming.

The simplest algorithm uses the following recursion to generate all combinations of length $m$ of a set $x_1,\ldots,x_n$:

  • If $m = 0$ then output the empty set.
  • Otherwise, for each $m \leq i \leq n$, generate all combinations of length $m-1$ of $x_1,\ldots,x_{i-1}$, and add $x_i$ to all of them.
$\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.