Recursive Combination Algorithm Implementation in C++


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.

tex_ae4f8efc2d46164e8dcae491c9ddb4a1 Recursive Combination Algorithm Implementation in C++ algorithms c / c++ recursive

For example, tex_9b85cb0958debee90ef091dddb418bc0 Recursive Combination Algorithm Implementation in C++ algorithms c / c++ recursive 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.

recursive-comb Recursive Combination Algorithm Implementation in C++ algorithms c / c++ recursive

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) —

GD Star Rating
loading...
537 words
Last Post: Flash Your Webpage Title - Javascript Code Snippet
Next Post: C/C++ Coding Exercise - seq Implementation on Windows Platform

The Permanent URL is: Recursive Combination Algorithm Implementation in C++

6 Comments

  1. Vladimir
  2. James
    • James
  3. alfredo stochiero

Leave a Reply