Tuesday, December 20, 2011

Getting Combinations in c++

we had programming exercise and I needed to put a function to return K combinations from N numbers starting from 1
So for example of N = 10, K = 3
I would have combinations starting from
1,2,3 - 1,2,4 – 1,2,5 – 1,2,6 – … and so on  till 8,9,10
I found some function to do this in c# here
http://stackoverflow.com/questions/548402/list-all-possible-combinations-of-k-integers-between-1-n-n-choose-k
I took the same algorithm and wrote it in c++ using vectors
below is the 2 functions I used, getCombinations will return the combinations vector
vector<vector<int> > getCombinations(int n, int k)
{
    // define variales
    vector<vector<int> > combincations;
    vector<int> row;
    for(int i=0;i<k; i++)
    {
        row.push_back(0);
    }
    row[0] = 1;
    // call the iterate function
    iterate(0,combincations,row,n,k);
    return combincations;
}
void iterate(int i, vector<vector<int> > &c, vector<int> &row, int n, int k )
{
    /// i represents the current index in the row vector that is used to fill the c matrix with combinations
    // set the i term to previous term +1
    if(i>0)
    {
        row[i] = row[i-1] +1;
    }
    //for loop to increment the current cell in the row till it reachs n-k+i+1
    // we are using n-k+i because we want to reach different values depending on the index
    // for example in N = 10, k = 3, first cell will increase till 8, second till 9, third till 10
    // so the last combination is 8,9,10
    for(;row[i] <= (n - k + i + 1);row[i]++)
    {
        // if this is not the last index, call iterate with next index
        // else fill in the combinations matrix
        if (i < k - 1)
        {
            iterate(i + 1, c, row, n, k);
        }
        else
        {
            vector<int> combination = row; //copying the row content
            c.push_back(combination); // adding the row to combinations vector
        }
    }
}