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

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.)

The solution uses recursion at two levels:

• find combinations C(n, k): k steps
• find a sequence of n/k C(n, k) : n/k steps

To avoid a repetition of the groups in a different order: first element in each group must be less or equal than the position. A consequence is that the first group always starts with 1, by example.

Some results:

• 3 combinations for 4-2
• 10 combinations for 6-3
• 15 combinations for 6-2

I would like to know the calculation formula to further validate the results.

#include <vector> #include <set> #include <iostream> #include <cassert> #include <fstream> namespace lan { struct Solution { virtual bool Next(const std::vector<unsigned>&) = 0; }; void SetCombination(const size_t, const size_t, Solution*); struct ToPrint: public Solution { ToPrint(): m_cnt(0) {}; void Print(const std::vector<unsigned>& solution, std::ostream& out, size_t grouped = 0) { assert(grouped <= solution.size()); if (grouped) out<<"{"; for (size_t i = 0; i < solution.size(); ++i) { if (i) { if (grouped && !(i%grouped)) out<<"} {"; else out<<" "; } out<<solution[i]; } if (grouped) out<<"}"; out<<std::endl; } bool Next(const std::vector<unsigned>& solution) { Print(solution, std::cout); ++m_cnt; return true; } size_t Count() const {return m_cnt;}; protected: size_t m_cnt; }; struct GroupOf: public ToPrint { typedef ToPrint Super; GroupOf(int length, int group, bool print): m_length(length), m_group(group), m_print(print) { assert(!(length%group)); //m_out.open("out.txt"); //assert(m_out); } bool Next(const std::vector<unsigned>& partial) { assert(m_group == partial.size()); size_t i; for (i = 0; i < m_group-1; ++i) assert(partial[i] < partial[i+1]); // first element in each partial solution must be <= position (to avoid groups recombination) if (partial[0] > 0) return false; // add the next group to the solution assert(m_sum <= m_length-m_group); size_t j, k; for (i = j = k = 0; (i < m_length) && (j < m_group); ++i) { if (!m_solution[i] && (k++ == partial[j])) { j++; m_solution[i] = j + m_sum; } } assert(j == m_group); // process a solution or go after the next group, recursively m_sum += m_group; if (m_sum == m_length) { std::vector<unsigned> print; Translate(m_solution, print); if (m_print) //Print(print, m_out, m_group); Print(print, std::cout, m_group); assert(Validate(print)); ++m_cnt; } else SetCombination(m_length-m_sum, m_group, this); // restore "stack" of recursive calls m_sum -= m_group; for (i = 0; i < m_length; ++i) if (m_solution[i] > m_sum) m_solution[i] = 0; return true; }; void Start() { m_sum = 0; m_solution.assign(m_length, 0); SetCombination(m_length, m_group, this); }; protected: // transform positions to "real" solution static void Translate(const std::vector<unsigned>& a, std::vector<unsigned>& b) { b.resize(a.size()); for (size_t i = 0; i < a.size(); ++i) { assert(a[i]); b[a[i]-1] = 1+i; } } #ifdef _DEBUG static bool Validate(const std::vector<unsigned>& a) { std::set<unsigned> elements; for (size_t i = 0; i < a.size(); ++i) elements.insert(a[i]); if (elements.size() != a.size()) return false; return true; } #else static bool Validate(const std::vector<unsigned>&) { return true; } #endif private: GroupOf& operator= (const GroupOf&); protected: const size_t m_length; const size_t m_group; const bool m_print; size_t m_sum; std::vector<unsigned> m_solution; //std::ofstream m_out; }; // get a 'length' by 'group' combination; since it's strictly ordered ( = ... the order doesn't matter), the first index is "next" bool SetCombination(const size_t length, const size_t group, size_t next, std::vector<unsigned>& solution, Solution* cbk) { assert(length); assert(cbk); assert(group <= length); assert(next < length); for (size_t i = next; i < length; ++i) { solution.push_back(i); next = i+1; if (solution.size() == group) { if (!cbk->Next(solution)) return false; } else if (next != length) { if (!SetCombination(length, group, next, solution, cbk)) return false; //break; } solution.pop_back(); } return true; } void SetCombination(const size_t length, const size_t group, Solution* cbk) { std::vector<unsigned> solution; (void)SetCombination(length, group, 0, solution, cbk); } size_t Test(size_t total, size_t grouped, bool print = false) { GroupOf test(total, grouped, print); test.Start(); return test.Count(); } } 

All the results until now:

assert(3 == lan::Test(4, 2)); assert(10 == lan::Test(6, 3)); assert(15 == lan::Test(6, 2)); assert(126 == lan::Test(10, 5)); assert(280 == lan::Test(9, 3)); assert(945 == lan::Test(10, 2)); if (0) { assert(1716 == lan::Test(14, 7)); assert(5775 == lan::Test(12, 4)); assert(126126 == lan::Test(15, 5)); // 1s, Release } 

std::next_permutation may help:

#include <algorithm> #include <iostream> int main() { int v[] = {1, 2, 3, 4, 5, 6}; do { std::cout << "{" << v[0] << "," << v[1] << "," << v[2] << "}, " << "{" << v[3] << "," << v[4] << "," << v[5] << "}" << std::endl; } while (std::next_permutation(std::begin(v), std::end(v))); return 0; } 

which output (6! solutions)

{1,2,3}, {4,5,6} {1,2,3}, {4,6,5} ... {6,5,4}, {3,1,2} {6,5,4}, {3,2,1} 

Or if order inside group doesn't matter, you may try the following:

#include <algorithm> #include <iostream> int getNextIndex(const int (&v)[6], int start, int value) { return std::find(std::begin(v) + start, std::end(v), value) - std::begin(v); } void print(const int (&v)[6]) { // Filter if you want that // `{1, 2, 3}, {4, 5, 6}` is equivalent to `{4, 5, 6}, {1, 2, 3}` if (getNextIndex(v, 0, 1) > getNextIndex(v, 0, 2)) return; //if (getNextIndex(v, 0, 2) > getNextIndex(v, 0, 3)) return; // And so on if you have more groups const char* sep[] = {", ", ", ", "}"}; for (int i = 1; i != 3; ++i) { int index = -1; std::cout << "{"; for (int j = 0; j != 3; ++j) { index = getNextIndex(v, index + 1, i); std::cout << 1 + index << sep[j]; } std::cout << ", "; } std::cout << std::endl; } int main() { int v[] = {1, 1, 1, 2, 2, 2}; do { print(v); } while (std::next_permutation(std::begin(v), std::end(v))); return 0; } 

which outputs (10 solutions):

{1, 2, 3}, {4, 5, 6}, {1, 2, 4}, {3, 5, 6}, {1, 2, 5}, {3, 4, 6}, {1, 2, 6}, {3, 4, 5}, {1, 3, 4}, {2, 5, 6}, {1, 3, 5}, {2, 4, 6}, {1, 3, 6}, {2, 4, 5}, {1, 4, 5}, {2, 3, 6}, {1, 4, 6}, {2, 3, 5}, {1, 5, 6}, {2, 3, 4},