We're a community of 1077K IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,076,174 Members — Technology Publication meets Social Media

# Combination Generation

By Ron Whittle on Feb 24th, 2011 10:05 pm

As a companion article to my Permutation Generation, I now present Combination generation.

This snippet will do a lazy generation of the combinations of a set of objects. Each combination has a grouping size (number of items in each combination). If you need a different grouping size, you'll have to create a new instance.

As was done in the permutation class, you can request specific lexical combinations either by calling the method GetCombination or by using the index operator.

How to use:
First you'll need an array of object. Call the Combination constructor passing the array and the grouping size. Since this is a generic class, you'll have to provide the class type of the array (like all generics).

The test example will take an array of six strings, with a grouping size of 3, and:

• Display how many different combinations there are.
• Display all the combinations.
• Display the fourth lexical combination using a method call.
• Display the sixth lexical combination using indexing.
using System;
using System.Text;
using Whittle.Math;

namespace Whittle {
class Program {
static void Main(string[] args) {
int counter = 0;
String[] myItems = { "A", "B", "C", "D", "E", "F" };
Combination<string> myCombos = new Combination<string>(myItems, 3);

Console.WriteLine("For {0} items there are {1} combinations", myItems.Length, myCombos.NumberOfCombinations);
Console.WriteLine();
foreach (String[] perm in myCombos) {
Console.Write("{0} ", SeqFormat(perm));
counter = (counter + 1) % 6;
if (counter == 0) Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine("The fourth lexical combination is {0}", SeqFormat(myCombos.GetCombination(4)));
Console.WriteLine();
Console.WriteLine("The sixth lexical combination is {0}", SeqFormat(myCombos[6]));

}

static String SeqFormat(String[] strings) {
StringBuilder sb = new StringBuilder();
sb.Append("[");
foreach (String s in strings) {
sb.Append(s);
}
sb.Append("]");

return sb.ToString();
}
}
}

How it works:
The wikipedia article explains it better than I ever could :)

Limitations:
Because this requires the use of factorials (even though they are generated in a unique way) it is possible to overflow the int variables used to generate the combinations. If you really need larger combinations, try changing all the int values to long, or BigInteger.

Acknowlegments:
As before, my sources are wikipedia and the 2006 MSDN Article "Test Run" by Dr. James McCaffrey.

using System;
using System.Collections;

namespace Whittle.Math {
/// <summary>
/// Class to generate all the combinations of an array of objects. This code
/// is released under the GPL v3 license with the aditional restriction that
/// any use in a public product requires notification of the author.
/// </summary>
/// <typeparam name="T">The type of objects</typeparam>
public class Combination<T> : IEnumerable, IEnumerator {
private T[] items;
private int atATime;
private int current = -1;
private long count;

/// <summary>
/// Constructor for the Combination class
/// </summary>
/// <param name="list">Array of objects used to build combinations</param>
/// <param name="n">Number of items in each combination</param>
public Combination(T[] list, int n) {
this.items = list;
this.atATime = n;
this.count = Choose(this.items.Length, this.atATime);
}

/// <summary>
/// Gets the specific lexical combination. Note that combinations are numbered from 0 to NumberOfCombinations - 1
/// </summary>
/// <param name="n">Lexical combination to return</param>
/// <returns>Array containing the nth lexical combination</returns>
public T[] GetCombination(long n) {
if (n >= count) {
throw new ArgumentOutOfRangeException(String.Format("Requested combination ({0}) exceeds number of combinations ({1})", n, count));
}

T[] result = new T[this.atATime];
int[] ans = new int[this.atATime];

int a = this.items.Length;
int b = this.atATime;
long x = (Choose(a, b) - 1) - n;

for (int i = 0; i < this.atATime; i++) {
ans[i] = LargestV(a, b, x);
x -= Choose(ans[i], b);
a = ans[i];
b--;
}

for (int i = 0; i < this.atATime; i++) {
result[i] = items[items.Length - 1 - ans[i]];
}

return result;
}

/// <summary>
/// Number of combinations for this specific set of objects and grouping size
/// </summary>
public long NumberOfCombinations {
get {
return count;
}
}

/// <summary>
/// Method to allow indexing into combinations.
/// </summary>
/// <param name="n">Lexical combination to return</param>
/// <returns>Array containing the nth lexical combination</returns>
public T[] this[int n] {
get {
return GetCombination(n);
}
}

// The next two methods are used to calculate the combinadic. See
// Wikipedia article at http://en.wikipedia.org/wiki/Combinatorial_number_system
// and the 2006 MSDN Article "Test Run" by Dr. James McCaffrey
private int LargestV(int a, int b, long x) {
int v = a - 1;
while (Choose(v, b) > x) {
v--;
}
return v;
}

private long Choose(int n, int k) {
long result = 0;
int delta;
int max;

if (n < 0 || k < 0) {
throw new ArgumentOutOfRangeException("Invalid negative parameter in Choose()");
}
if (n < k) {
result = 0;
} else if (n == k) {
result = 1;
} else {
if (k < n - k) {
delta = n - k;
max = k;
} else {
delta = k;
max = n - k;
}
result = delta + 1;
for (int i = 2; i <= max; i++) {
checked {
result = (result * (delta + i)) / i;
}
}
}

return result;
}

#region IEnumerator & IEnumerable methods
IEnumerator IEnumerable.GetEnumerator() {
return this;
}

object IEnumerator.Current {
get {
return GetCombination(current);
}
}

bool IEnumerator.MoveNext() {
current++;
return (current < count);
}

void IEnumerator.Reset() {
current = -1;
}
#endregion
}
}

Good day Bro

I have a new post here

codeholic
Newbie Poster
5 posts since Jul 2011
Reputation Points: 9
Skill Endorsements: 0
Post: Markdown Syntax: Formatting Help

You
View similar articles that have also been tagged: