N choose K, K-N, K-2N, etc, recursion within recursion

Question

I know how to use recursion to generate all possible combinations, i.e. N choose K. But how to create all the possible N/K-groups of K? N is of course always divisible by K. To clarify: for example, if N is 20 and K is 4, then I want to generate all the possible five-groups-of-four. And if, say, N contains 1,2,3...20 and K is 4, then one such grouping is {1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16},{17,18,19,20}. Let's assume that N is relatively small, so recursion is feasible

I feel like this is a recursion-within-recursion problem, since generating all possible single-group-of-four (aka N choose K) requires recursion, and then generating the next group of four becomes N - 4 choose K, and the next N - 8 choose K, etc. But I'm having trouble implementing this...any help?

Answer 1

Terminology: What you want is all partitions of a set of N elements into parts of size K each. There are n!/((k!)^(n/k) (n/k)!) such partitions (see answer on math.SE).

To avoid overgeneration, let's decide on a "canonical form" for each partition: let's say it is to write each part in increasing order, and then write these parts themselves in increasing order of their smallest element.

Now you can visualize generation of a partition as a process of dropping balls numbered 1 to N, one by one, into N/K bins. The constraint that each bin (part) must be in increasing order is then automatically satisfied (of course you should "read" each bin in the order in which elements were inserted), and the constraint on the parts is satisfied if we make sure we don't skip an empty bin before populating the next one.

Now to translate that into code. Let's model our partition (or bunch of bins) as a vector of vectors.

#include <iostream>
#include <vector>
#include <cassert>

std::vector< std::vector<int> > partition;
int N, K;
int num_partitions_found = 0;

void OutputPartition();

In general, when generating structures recursively (or coding any recursive algorithm), your recursive function is given a particular "state", and tries each incremental way of extending that state. Between different options, just make sure to bring the state back to what you were given.

So let's write our recursive function to be one that takes a state in which balls up to n-1 have been placed in bins, and extends the state by placing ball n in all possible places.

void GeneratePartitions(int n) {
  // When we've placed all N elements, output and stop.
  if (n == N + 1) {
    OutputPartition();
    return;
  }
  // Place ball n into each allowed bin.
  for (int i = 0; i < N / K; ++i) {
    // Cannot place into a full bin
    if (partition[i].size() == K) continue;
    // Cannot skip an empty bin
    if (i > 0 && partition[i-1].empty()) break;
    // Place the ball here: extending the state
    partition[i].push_back(n);
    // How to extend the new state is left to the recursive call
    GeneratePartitions(n + 1);
    // Make sure you restore state after each recursive call!
    partition[i].pop_back();
  }
}

That is the core of the recursion. The rest of the program is scaffolding.

void OutputPartition() {
  assert(partition.size() == N/K);
  ++num_partitions_found;
  for (int i = 0; i < N/K; ++i) {
    assert(partition[i].size() == K);
    std::cout << "{";
    for (int j = 0; j < K; ++j) {
      std::cout << partition[i][j] << (j == K - 1 ? "}" : ", ");
    }
    if (i < N/K - 1) std::cout << ", ";
  }
  std::cout << std::endl;
}

int main() {
  std::cin >> N >> K;
  assert(N % K == 0);
  partition.resize(N / K);
  GeneratePartitions(1);
  std::cout << num_partitions_found << " found" << std::endl;
}

Note: this post is a literate program: if you put the code snippets together, you have a valid working program.

Alternatively, in case you'd like to try the program (see how fast it runs, etc.), a different version is here on github: it doesn't use global variables, uses a plain array (faster) for the partition, and prints all found partitions only for small N (edit the code to change it).

To return to your question, we saw that by carefully thinking about the problem for a little while, you can avoid having different kinds of recursion. Even if you do, the general recipe for writing a recursive program stands: write a recursive function that takes a state, extends it by one step in all possible ways (passing off further extension of these states to a recursive call), and then cleans up to its original state. (Sometimes, when the state is small, you don't have to do any cleanup—you can pass along the state with the function call—but other times it's cleaner to have the state be shared by the recursive calls.)