Combination Algorithm: Print all Possible Combinations of R

By : Alyssa Walker Alyssa Walker
Hours Updated

What is the Combination?

The Combination is a kind of arrangement of some given objects. In mathematical terms, Combination is a set of choices/selection of items from a unique set of items/objects. Here, the order of the items doesn’t matter. It is also known as the method to calculate the total outcome of an event, where the order of the outcome doesn’t matter.

For example, you’re given a bag with 5 different colors and asked to generate a pattern with any 3 colors. You can also pick any 3 colors out of 4, then arrange them in different orders.

Let’s assume the colors are RGYBI(R= Red, G= Green, Y= Yellow, B= Blue, I= Indigo). So, the possible pattern can be RGB, RGY, etc.

Let’s have a look at the following figure:

Color Combination
Color Combination

Explanation:

  • Take any 4 colors out of 5 and list them
  • From each block of 4 colors,, pick any 3 and list them all. For example, we only picked “RGBI” in the figure and showed 4 combinations.
  • There’s a theory behind it to calculate the total number of combinations we can make. A combination of r elements out of n can be mathematically presented as:
Formula of Combination

Formula of Combination

The sign “!” means the factorial. For example,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Say, 5! = 5*4*3*2*1 = 120

So, for our above problem, we have 5 colors meaning n = 5, and at any given time, we need to pick any 3. So, r = 3. After calculating, we get,

Combination

A total of 10 color combinations is possible for the above scenario.

The time complexity analysis for Combination

Now, let’s say, given an array of size n, we are asked to take r elements from the array and perform combinations of r elements.

If an array of size n is given, then it will take O(n2) time to perform the task. Also, if we want to remove the duplicate entry, then,

We need to perform the following steps:

Step 1) Sort the input array data in ascending manner. The Time Complexity of sorting is O(n*log(n)).

Step 2) Create another array containing a unique element from the given temporary array data.

Step 3) Then, perform the combination function.

So, total time complexity becomes = O(n2) + O(nLog(n)). We can consider it O(n2), as n2 is much larger than n*log(n).

Method-1: Fixed element with recursion

In this method, we’ll pick an element then find a combination of r-1 elements. As we’re picking an element from the rest of the element, we are doing recursively, and that’s why it’s called fixed element and recursion.

Let’s demonstrate the algorithm step by step with a diagram:

Fixed Element with Recursion

Steps are given below:

Step 1) In the first layer, take n-r+1 elements. Meaning we took 3 elements.

Step 2) Pick an element from the 2nd layer and take it up to n-r. So, if we take “R,” then with R, we can take G, Y, and B.

Step 3) Pick an element from the 3rd layer and take it up to the nth element, and form blocks containing 3 elements each.

The above figure is the return value from the recursion. Only the last layer will be printed.

Pseudo Code

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

Implementation in C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

Output:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Implementation in Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i & lt; = end and end - i + 1 & gt; = r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

Output:

R G Y 
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

Method 2 (Include and Exclude every element)

This method is based on Pascal’s identity. Previously we used recursion for calculating nCr. Here, the method is just divided instead of a complex loop.

According to Pascal’s identity,

nCr = (n-1)Cr + (n-1)C(r-1)

So, there’ll be 2 recursive logic for the recursive algorithm to find a Combination of r elements from a given array of size n.

  1. Element is included in the current Combination
  2. Element is excluded from the current Combination

Pseudo Code

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

Implementation in C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

Output:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Implementation in Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

Output:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

Handling Duplicate Combinations

Sometimes there might be duplicate elements in the input array.

For example,

  • The input array contains n = {5, 2, 3, 1, 5}.
  • Here, we can see that 5 is present for 2 times.
  • Now, if we want to run the code for this array, some combinations will be repeated.
  • We’ll find {5, 2, 5}, {5, 2, 3} etc or any combination that contain 5, will be repeated.

We can use these two methods:

  • Sort the input array. Sorting will take O(nlog(n)) time.
  • Then increase the value of i, while i value and i+1 value is same. Basically put the following two line of code in the Combination function.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

Using a dictionary or unordered map to track duplicate combinations

So, if we don’t want to sort the elements for tracking the duplicate, we can follow the given steps.

Step 1) Declare a global dictionary or hashmap.
Step 2) Push the generated Combination to the hashmap and increase the value by one. The combination is the key, and their occurrence are values.
Step 3) when the function is finished running, simply we’ll print all the keys from the hashmap or dictionary.

Here’s the implementation in python

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

Output: 

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

Here, you can see that the input was “RGYBIB.” Generally, there should occur some duplicate combinations. But as we used a dictionary and treated each Combination as the key, we can print only the unique Combination.

Now, if you write “print(unique_combination),” you can see each combination’s frequency. It will show like this:

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

So, we can see that RGB, RYB, GYB have occurred 2 times. The time complexity of inserting the key to a dictionary is basically O(1). So, if you use a dictionary, then the total time complexity for running the code will be:

O(1) + O(n*n)

Equivalent to O(n*n).

Using the previous method to track duplicate, we need O(n*log(n)) for sorting; for comparing, we need O(n), and the function itself takes O(n*n). Total time complexity will be:

O(n*log(n)) + O(n) +O(n*n)

You Might Like: