Printing all subsets

Question

I have tried to incorporate comments from my previous code review into this. So, I am hoping for less mistakes. If you spot any, please let me know mercilessly!

#include <iostream>
#include <queue>

void printsub(int* p, int len, std::queue<int> q) {

    if (!len) {
        while(!q.empty()) {
            std::cout << q.front() << " ";
            q.pop();
        }
        std::cout << "\n";
        return;
    }

    std::queue<int> t1(q);
    t1.push(p[0]);
    printsub(&(p[1]), len - 1, t1);

    std::queue<int> t2(q);
    printsub(&(p[1]), len - 1, t2);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};                                     

    std::queue<int> q;
    printsub(arr, ((sizeof(arr))/(sizeof(arr[0]))), q);
}

Answer 1

You could translate this recursive Python code.

def xcombinations(items, n):
  if n==0: yield []
  else:
    for i in xrange(len(items)):
        for cc in xcombinations(items[:i]+items[i+1:],n-1):
            yield [items[i]]+cc

in C++ roughly (untested, but you get the idea):

using std::set;

set<set<int>> xcombinations(const set<int> &items, size_t n) {
    set<set<int>> result; // collect for 'return' instead of pythons 'yield'
    if(n==0) return result;
    for(int elem : items) { // ranged-for from C++11
        // 'items' without 'elem', python 'items[:i]+items[i+1:]'
        set<int> temp(items); // copy
        temp.erase(elem); // ...or use 'std::remove_copy_if'
        for(auto cc : xcombinations(temp, n-1)) { // ranged-for from C++11
            cc.insert(elem);
            result.insert(cc); // python yield;
        }
    }
    return result;
}

Note that auto cc creates a copy in the inner loop, where one can add elem before adding it to result.

Instead if the new C++11 ranged-for and auto one can of course just use lengthy iterator-based for-loops.

Using vector instead of set would also work, I guess. There are no set-operations involved here. Actually, now that I think of it, vector would be much better... hmm...

One could save some copying by pulling temp out of the loop, initialize it with a a size of n-1 and use std::remove_copy_if to put the values into it. And if one does that, one can even save the copy of all values by just replacing one in the inner loop, but I can not see how right away.

Ah, well and you need a printing routine, of course.

std::ostream& operator<<(std::ostream &os, const set<int>& items) {
    for(int elem: items)
        os << elem << " ";
    return os;
}
std::ostream operator<<(std::ostream &os, const set<set<int>>& itemss) {
    for(const auto &cc: itemss)
        os << "  {" << cc << "}\n";  // or use 'ostream_iterator' on 'cc'
    return os;
}

int main(/*...*/) {
    set<int> data = {1, 2, 3, 4, 5, 6}; // C++11 init-list
    std::cout << xcombinations(data, data.size()) << std::endl;
}