Combination Algorithm: Print all Possible Combinations of R
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:
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:
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,
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:
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.
- Element is included in the current Combination
- 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)