Return to Revisions

I had the same problem, but for any n multichoose k. I also needed a non-recursive algorithm to resolve it as my performance requirements are strict.

I couldn't find a non-recursive solution anywhere on the web, so I implemented one in C++ (for generic vectors) and C. See: http://github.com/ekg/multichoose, specifically multichoose.h:

template <class T>
std::vector< std::vector<T> > multichoose(int k, std::vector<T>& objects) {
    std::vector< std::vector<T> > choices;
    int j,j_1,q,r;
    r = objects.size() - 1;
    std::vector<T*> a, b; // combination indexes
    for (int i=0;i<k;i++) {
        a.push_back(&objects[0]); b.push_back(&objects[r]);
    }
    j=k;
    while(1){
        std::vector<T> multiset;
        for(int i=0;i<k;i++)
            multiset.push_back(*a[i]);
        choices.push_back(multiset);
        j=k;
        do { j--; } while(a[j]==b[j]);
        if (j<0) break;
        j_1=j;
        while(j_1<=k-1){
            a[j_1]=a[j_1]+1;
            q=j_1;
            while(q<k-1) {
                a[q+1]=a[q];
                q++;
            }
            q++;
            j_1=q;
        }
    }
    return choices;
}