Generation of all subsets k of size {0, 1, 2, ... n-1}

Question

I want to generate all arrays of k subsets of {0, 1, 2, ..., n-1} in C ++. In Haskell, I would do:

 sets 0 n = [[]] sets kn = [i:s | i <- [0..n-1], s <- sets (k-1) i] 

Or in Python:

 def sets(k, n): if k == 0: return [()] return ((i,)+s for i in range(n) for s in sets(k-1, i)) 

So, for example, (line breaks are added for clarity)

 ghci> sets 2 8 [[1,0], [2,0],[2,1], [3,0],[3,1],[3,2], [4,0],[4,1],[4,2],[4,3], [5,0],[5,1],[5,2],[5,3],[5,4], [6,0],[6,1],[6,2],[6,3],[6,4],[6,5], [7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6]] 

What would be a "C ++ method"? Please note that I am not asking how to solve the problem. I ask what data types will be considered "normal" C ++ programmers.

^{(For reference, I am dimly familiar with C ++ and a little familiar with C.)}

Answer 1

Here's a naive, recursive approach that implements the classic combinatorial identity:

 binom(n + 1, k + 1) = binom(n, k + 1) + binom(n, k) 

 #include <set> typedef std::set<int> intset; std::set<intset> subsets(std::size_t k, intset s) { if (k == 0 || s.empty() || s.size() < k) { return { { } }; } if (s.size() == k) { return { s }; } auto x = *s.begin(); s.erase(s.begin()); std::set<intset> result; for (auto & t : subsets(k - 1, s)) { auto r = std::move(t); r.insert(x); result.insert(std::move(r)); } for (auto & t : subsets(k, s)) { results.insert(std::move(t)); } return result; } 

Using:

 auto ss = subsets(3, {0, 1, 2, 3, 4}); 

Full example:

 #include <iostream> #include <string> #include <prettyprint.hpp> int main(int argc, char * argv[]) { if (argc != 3) return 1; auto k = std::stoul(argv[1]); auto n = std::stoul(argv[2]); intset s; for (auto i = 0U; i != n; ++i) s.insert(i); std::cout << subsets(k, s) << std::endl; } 

Answer 2

In Rosetta Code, the implementation works by taking the first k entries of the permutations of the list 0, 1, ..., n-1 . It uses C ++ STL.

Answer 3

The concept of a set of all subsets is called a power set , and little is written on Wikipedia. One section is even devoted to algorithms for doing what you want. This particular problem requests subsets of limited power for power gain. You should probably use std::set .

Answer 4

A quick implementation (using recursion) of this in C would be as follows:

 #include <stdio.h> #define N 8 #define K 3 void print_combination(int* combination, int k) { int i; for (i = 0; i < k; i++){ printf("%d ", combination[i]); } printf("\n"); } void find_all_combinations(int idx, int* in_use, int* combination, int n, int k) { int i; if (idx == k){ print_combination(combination, k); return; } for (i = 0; i < n; i++){ if (in_use[i]){ continue; } in_use[i] = 1; combination[idx++] = i + 1; find_all_combinations(idx, in_use, combination, n, k); combination[--idx] = 0; in_use[i] = 0; } } int main(void) { /* Ensure that the arrays are initialized with zeroes. */ int in_use[N] = {0}; int curr_combination[K] = {0}; find_all_combinations(0, in_use, curr_combination, N, K); return 0; }