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
}
}
}
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
}
}
}
No comments:
Post a Comment