The real challenge was to be able to generate all possible combinations. First of all, I tried using 'while' loop, breaking out of the loop once all the combinations are listed. But it was missing out some of the combinations. Then, I decided to solve the problem using recursion.
I had used the exhaustive approach to ensure that every combination is traversed. The methodology is that you create a tree by selecting one of the numbers of an array as a root and add the remaining numbers of an array as its child. For each child, the index values that have not occurred when traversing the path from the root to that child are added as its children. This process is repeated for every child until the depth of this tree is equal to r-1. Each array value gets selected as a root, so there will be n trees with depths r-1.
For example, if there is an array of 4 indices with values 1,2,3 and 4, and you want to find out combinations of 3 in it, then, you will get the following trees:
If we keep track of all paths traversed from root to leaf for each of the trees obtained, then we will get all the permutations in which order is important. But, the task is to have list of combinations. Hence, we would check each path elements and compare it with the elements of the paths already traversed. This path is stored only if its elements do not exactly match with the elements of the previous paths. Thus, we will get list of combinations in which order does not matter.
In my implementation, there is a loop that goes through a single iteration of an integer array. In each iteration, I consider the index value to be a root element and then build a tree with the remaining index values. This is done by calling the method "GetCombinations()" that does the main job. This method is recursively called to build a tree.
After building a tree, all the paths from root to leaf are traversed and stored in the global list object "Combinations" only if they are unique,i.e., their elements do not match with a path already in the list. This process of building a tree and traversing and storage of paths is repeated for each iteration. At first, I created a method which manually checks the elements of each of the paths of "Combinations" list, but the execution became tremendously slow even for small numbers as this method was called very often. Therefore, I used hashtable to store the paths along with "Combinations" so that checking could be done faster.
The method guarantees retrieval of all possible combinations. However, it became notably slower as 'n' is increased (typically above 100). Here is the code for combinations:
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
namespace CombinationGenerator
{
class Program
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; //predefined numbers. n=20 in this case
int UsingNum;
int r = 2;
List
List
List
Hashtable ht = new Hashtable();
public void Combinations()
{
values = new List
for (int i = 0; i < arr.Length; i++)
{
values.Add(arr[i]);
}
dummy = new List
for (int index = 0; index < values.Count; index++)
{
UsingNum = dummy[0]; // it contains the index value that is the root in particular iteration
dummy.RemoveAt(0);
GetCombinations(new List
}
for (int i = 0; i < combinations.Count; i++)
{
int[] p = combinations[i];
foreach (int a in p)
Console.Write(a.ToString() + " ");
Console.Write("\n");
}
Console.WriteLine("No. of combinations =" + combinations.Count);
}
public void GetCombinations(List
{
string str = "";
for (int i = 0; i < temp.Count; i++)
{
if (diff > 1) // Checking the depth of tree which has to be equal to 'r-1'
{
int num = temp[i];
List
a.Add(num);
List
b.RemoveAt(i);
GetCombinations(a, b, r - (a.Count + 1));
}
else if (diff == 1)
{
str = "";
if (hold.Count == 0)
{
int[] comb = { UsingNum, temp[i] };
Array.Sort(comb);
for (int j = 0; j < comb.Length; j++)
{
str = str + comb[j] + ",";
}
str.Remove(str.Length - 1);
if (!ExistInCombinationSet(str))
{
combinations.Add((int[])comb.Clone());
ht.Add(str, (int[])comb.Clone());
}
}
else
{
int[] comb = new int[hold.Count + 2];
comb[0] = UsingNum;
for (int j = 0; j < hold.Count; j++)
{
comb[j + 1] = hold[j];
}
comb[hold.Count + 1] = temp[i];
Array.Sort(comb);
for (int j = 0; j < comb.Length; j++)
{
str = str + comb[j] + ",";
}
str.Remove(str.Length - 1);
if (!ExistInCombinationSet(str))
{
combinations.Add((int[])comb.Clone());
ht.Add(str, (int[])comb.Clone());
str = "";
}
}
}
}
}
public bool ExistInCombinationSet(string str) // Method to check whether the traversed path is unique
{
if (ht.ContainsKey(str))
return true;
else
return false;
}
static void Main(string[] args)
{
Program prg = new Program();
prg.Combinations();
Console.ReadLine();
}
}
}
Suggestions for improving the code are most welcome. The code can be downloaded from here.
