The combination is a frequently-used technique that choose a number of items from a whole data set (sequence is not important). For example, to choose 2 items from 3, we have:
1 2 1 3 2 3
So please bear in mind that sequence doesn’t matter, so 1 2 is the same as 2 1.
The total number of combination of choosing m items from n can be computed by.
For example, meaning that there are 10 different solutions choosing 3 items from 5.
So, how do we express this in recursive relations?
For the first item, we can pick from item n to m and then we can choose m-1 items from the n-1 items. Let’s make it in C/C++ code. We need to store the sequence in a array, which can be static or dynamic created.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | /* HelloACM.com */ #include <iostream> using namespace std; void comb(int n, int r, int *arr, int sz) { for (int i = n; i >= r; i --) { // choose the first element arr[r - 1] = i; if (r > 1) { // if still needs to choose // recursive into smaller problem comb(i - 1, r - 1, arr, sz); } else { // print out one solution for (int i = 0; i < sz; i ++) { cout << arr[i] << " "; } cout << endl; } } } int main() { const int N = 5; const int M = 3; int *arr = new int[M]; comb(N, M, arr, M); delete []arr; return 0; } |
/* HelloACM.com */ #include <iostream> using namespace std; void comb(int n, int r, int *arr, int sz) { for (int i = n; i >= r; i --) { // choose the first element arr[r - 1] = i; if (r > 1) { // if still needs to choose // recursive into smaller problem comb(i - 1, r - 1, arr, sz); } else { // print out one solution for (int i = 0; i < sz; i ++) { cout << arr[i] << " "; } cout << endl; } } } int main() { const int N = 5; const int M = 3; int *arr = new int[M]; comb(N, M, arr, M); delete []arr; return 0; }
The above is simple and handy if you want to list all combinations given n and m. Of course, when the values are large enough, a possible stack overflow will occur when recursion depths become large.
You may be interested to read this also: The Combination Function and Iterator using Depth First Search Algorithm
Also, we can use the bitmasking algorithm to do the combination: Using Bitmasking Algorithm to Compute the Combinations of an Array
Also, we can use the backtracking to implement a iterative combination – as described in this post.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Flash Your Webpage Title - Javascript Code Snippet
Next Post: C/C++ Coding Exercise - seq Implementation on Windows Platform
You never release the memory and it is not a good practice. So… you should have delete[] arr;
Thank you for your feedbacks, code updated.
Hello, Thanks a lot of you.
Your source code is very helpful for me.
But I want to know normal algorithm. Not Recursive.
And I am beginner. so I could not edit your source code.
Please Help me.
Regardly…
Sorry, I means thant sorted order.
123
124
125
…….
245
345
Very nice code. It helped me a lot to understand recursive function. What if I wanted to print on the screen, the number of possible combinations , instead of the combinations itselves ? In this example with 5 and 3, how could the program print ” the possible combinations are 10 “
you could do
cout << "the possible combinations are " << m! / n! (m - n)!