Here is a program in Java that prints all unordered unique
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
- the first
curSubset subsets have been specified by
- the first
N - toFill numbers in the current subset,
subsetsHolder[curSubset] have been specified in
subsetsHolder[curSubset][0:N - toFill] and
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.
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.
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]. Recurse to fill the next number in the current subset.
- 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.