n choose k

[Deviouscola]

I can generate all the possible ways to choose 3 things out of 6 things with the following code (order doesn't matter here).

for(int i = 0; i < 6; ++i){
    for(int j = i+1; j < 6; ++j){
        for(int k = j+1; k < 6; ++k){
            cout << i << " " << j << " " << k << endl;
        }
    }
}

The problem is that I need to vary the number of items I'm choosing. Which means I have to vary the number of nested loops. Any ideas as to how I could do this? I want to know all the possible ways to choose k things out of n things, where k goes from 1 to some number less than n. I haven't had much experience writing recursive methods, but it seems like recursion might be the best way to go. Someone push me in the right direction please!

[Soko]

When in doubt, consult Donald Knuth!

http://portal.acm.org/citation.cfm?id=1036677&dl=&coll=

Donald Knuth has a selection of algorithms to choose from, or so I have heard.

If you want more of a push than that (a.k.a. don't want to find the book), let me know, and I will see what I can dig up. I seem to remember something from a math class I took once about something similar to this.

[Deviouscola]

This solution should work, at least it did when I went through it on paper. It's my own invention... It complies but produces a 'bus error' (I'm working on a mac). I'm guessing it's because I'm not using pointers the right way.

Basically, I made a class called 'For_Loop' which is supposed to behave like it sounds. A For_Loop object is made for each item that is being chosen. The For_Loops are then connected/nested with their pointer members.

Can you see any errors?

#include <iostream>
#include <vector>

using namespace std;

class For_Loop
{
    public:
        For_Loop(int init, int limit);
        ~For_Loop();
        void initialize(int val){ i = val; }
        void set_outter(For_Loop * outter){ p_outerLoop = outter; }
        void set_inner(For_Loop * inner){ p_innerLoop = inner; }
        void executeLoop(void);
        void met_condition(void);
        void print_thing(void);
    private:
        For_Loop * p_outerLoop;		//the outer loop
        For_Loop * p_innerLoop;		//the inner loop
        int i;		//thing to be selected
        int stop;
};

For_Loop::For_Loop(int init, int limit){
    p_outerLoop = NULL;
    p_innerLoop = NULL;
    i = init;
    stop = limit;
}

void For_Loop::executeLoop(void){
    if(p_innerLoop){
        p_innerLoop->executeLoop();	//inner loops must run first
    }else{
        while(i < stop){
            p_outerLoop->print_thing();
            cout << " " << i << endl;
            ++i;
        }
        p_outerLoop->met_condition();
        executeLoop();
    }
}

void For_Loop::print_thing(void){
    if(p_outerLoop){
        p_outerLoop->print_thing();
    }
    cout << " " << i;
}

void For_Loop::met_condition(void){
    if(i+1 >= stop){
        if(p_outerLoop){
            p_outerLoop->met_condition();
            p_innerLoop->initialize(i+1);
            executeLoop();
        }else{
            return;		//Done!
        }
    }else{
        ++i;
        p_innerLoop->initialize(i+1);
    }
}

void n_choose_k(int n_items, int k_items_to_choose);

int main() {
    //print all the ways to choose 2 to 4 things out of 10 things
    int k = 0;
    for(k = 2; k < 5; ++k){
        n_choose_k(10, k);
    }
    return 0;
}

void n_choose_k(int n_items, int k_items_to_choose){
    vector<For_Loop*> loops;
    For_Loop * temp;
    //create the loops
    for(int i = 0; i < k_items_to_choose; ++i){
        temp = new For_Loop(i, n_items);
        loops.push_back(temp);
    }
    //connect (nest) the loops
    for(int i = 0; i < k_items_to_choose-1; ++i){
        loops[i]->set_inner(loops[i+1]);
        if(i-1 >= 0) loops[i]->set_outter(loops[i-1]);
    }
    //run the loop structure
    loops[0]->executeLoop();
}

Thanks in advance, if you took the time to look at this.