3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Not enough for an answer but consider whether if(!len) makes sense. You are treating a number as a boolean value and while C++ allows this due to weak typing, it’s not a meaningful operation. Change it to an explicit check, if (len != 0). \$\endgroup\$ – Konrad Rudolph Jun 12 '12 at 10:29
3
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.