List of Combinations in C#

In Mathematics, Combination is the number of different ways of selecting 'r' elements from a set of 'n' elements where r <= n. The mathematical notation for combination is "nCr". As far as I have searched, I couldn't find such a functionality in .net framework. Therefore, I decided to create my own program that will generate the different combinations given the values of n and r. Calculating the number of combinations is straightforward. You need to calculate the factorials of n,n-r and r. This can be done by calling the factorial method thrice and then using the formula n!/((n-r)!r!) to compute the number of different combinations.

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 values; // holds the values of 'arr' array
List dummy; // temporary storage of values
List combinations = new List(); //contains the combinations
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(values);


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(), new List(dummy), r - 1);
}


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 hold, List temp, int diff) //Method for building trees and generating combinations
{
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 = new List(hold);
a.Add(num);
List b = new List(temp);
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.