Combinatorics in C#

Partly encouraged by this year’s Google Code Jam contest, but likely more so by the lack of any combinatorics functionality in the .NET Framework (still missing in most recent version 4.0), I thought I would put a bit of effort into writing efficient implementations of algorithms in C#. The following algorithms are implemented (between the GetPermutations and GetCombinations methods).

  • Permutations with repetition
  • Permutations without repetition
  • Combinations with repetition
  • Combinations without repetition

Worth noting is that the algorithms run purely in-place on the list, and involve no recursion (only a single while loop). While memory usage is minimal, they do of course still run in factorial (or equivalently exponential) time complexity, though it’s well known you can’t do any better than that if you require all permutations/combinations of a given size.

Download the full (documented) code for the utility class here.

All four algorithms have been sufficiently tested and verified for small lists, running on .NET 4.0 (Windows). I would be inclined to bet everything runs perfectly well on Mono too. Needless to say, bug reports and feedback are welcome.

using System;
using System.Collections.Generic;
using System.Diagnostics;

// Copyright (c) 2010 Alex Regueiro
// Licensed under MIT license, available at <http://www.opensource.org/licenses/mit-license.php>.
// Published originally at <http://blog.noldorin.com/2010/05/combinatorics-in-csharp/>.
// Version 1.0, released 22nd May 2010.
public static class CombinatoricsUtilities
{
// Error messages
private const string errorMessageValueLessThanZero = “Value must be greater than zero, if specified.”;
private const string errorMessagesIndicesListInvalidSize = “List of indices must have same size as list of elements.”;

/// <summary>
/// Gets all permutations (of a given size) of a given list, either with or without reptitions.
/// </summary>
/// <typeparam name=”T”>The type of the elements in the list.</typeparam>
/// <param name=”list”>The list of which to get permutations.</param>
/// <param name=”action”>The action to perform on each permutation of the list.</param>
/// <param name=”resultSize”>The number of elements in each resulting permutation; or <see langword=”null”/> to get
/// premutations of the same size as <paramref name=”list”/>.</param>
/// <param name=”withRepetition”><see langword=”true”/> to get permutations with reptition of elements;
/// <see langword=”false”/> to get permutations without reptition of elements.</param>
/// <exception cref=”ArgumentNullException”><paramref name=”list”/> is <see langword=”null”/>. -or-
/// <paramref name=”action”/> is <see langword=”null”/>.</exception>
/// <exception cref=”ArgumentException”><paramref name=”resultSize”/> is less than zero.</exception>
/// <remarks>
/// The algorithm performs permutations in-place. <paramref name=”list”/> is however not changed.
/// </remarks>
public static void GetPermutations<T>(this IList<T> list, Action<IList<T>> action, int? resultSize = null,
bool withRepetition = false)
{
if (list == null)
throw new ArgumentNullException(“list”);
if (action == null)
throw new ArgumentNullException(“action”);
if (resultSize.HasValue && resultSize.Value <= 0)
throw new ArgumentException(errorMessageValueLessThanZero, “resultSize”);

var result = new T[resultSize.HasValue ? resultSize.Value : list.Count];
var indices = new int[result.Length];
for (int i = 0; i < indices.Length; i++)
indices[i] = withRepetition ? -1 : i – 1;

int curIndex = 0;
while (curIndex != -1)
{
indices[curIndex]++;
if (indices[curIndex] == list.Count)
{
indices[curIndex] = withRepetition ? -1 : curIndex – 1;
curIndex–;
}
else
{
result[curIndex] = list[indices[curIndex]];
if (curIndex < indices.Length – 1)
curIndex++;
else
action(result);
}
}
}

/// <summary>
/// Gets all combinations (of a given size) of a given list, either with or without reptitions.
/// </summary>
/// <typeparam name=”T”>The type of the elements in the list.</typeparam>
/// <param name=”list”>The list of which to get combinations.</param>
/// <param name=”action”>The action to perform on each combination of the list.</param>
/// <param name=”resultSize”>The number of elements in each resulting combination; or <see langword=”null”/> to get
/// premutations of the same size as <paramref name=”list”/>.</param>
/// <param name=”withRepetition”><see langword=”true”/> to get combinations with reptition of elements;
/// <see langword=”false”/> to get combinations without reptition of elements.</param>
/// <exception cref=”ArgumentNullException”><paramref name=”list”/> is <see langword=”null”/>. -or-
/// <paramref name=”action”/> is <see langword=”null”/>.</exception>
/// <exception cref=”ArgumentException”><paramref name=”resultSize”/> is less than zero.</exception>
/// <remarks>
/// The algorithm performs combinations in-place. <paramref name=”list”/> is however not changed.
/// </remarks>
public static void GetCombinations<T>(this IList<T> list, Action<IList<T>> action, int? resultSize = null,
bool withRepetition = false)
{
if (list == null)
throw new ArgumentNullException(“list”);
if (action == null)
throw new ArgumentNullException(“action”);
if (resultSize.HasValue && resultSize.Value <= 0)
throw new ArgumentException(errorMessageValueLessThanZero, “resultSize”);

var result = new T[resultSize.HasValue ? resultSize.Value : list.Count];
var indices = new int[result.Length];
for (int i = 0; i < indices.Length; i++)
indices[i] = withRepetition ? -1 : indices.Length – i – 2;

int curIndex = 0;
while (curIndex != -1)
{
indices[curIndex]++;
if (indices[curIndex] == (curIndex == 0 ? list.Count : indices[curIndex - 1] + (withRepetition ? 1 : 0)))
{
indices[curIndex] = withRepetition ? -1 : indices.Length – curIndex – 2;
curIndex–;
}
else
{
result[curIndex] = list[indices[curIndex]];
if (curIndex < indices.Length – 1)
curIndex++;
else
action(result);
}
}
}

/// <summary>
/// Gets a specific permutation of a given list.
/// </summary>
/// <typeparam name=”T”>The type of the elements in the list.</typeparam>
/// <param name=”list”>The list to permute.</param>
/// <param name=”indices”>The indices of the elements in the original list at each index in the permuted list.
/// </param>
/// <returns>The specified permutation of the given list.</returns>
/// <exception cref=”ArgumentNullException”><paramref name=”list”/> is <see langword=”null”/>. -or-
/// <paramref name=”indices”/> is <see langword=”null”/>.</exception>
/// <exception cref=”ArgumentException”><paramref name=”indices”/> does not have the same size as
/// <paramref name=”list”/>.</exception>
public static IList<T> Permute<T>(this IList<T> list, IList<int> indices)
{
if (list == null)
throw new ArgumentNullException(“list”);
if (indices == null)
throw new ArgumentNullException(“indices”);
if (list.Count != indices.Count)
throw new ArgumentException(errorMessagesIndicesListInvalidSize, “indices”);

var result = new T[list.Count];
for (int i = 0; i < result.Length; i++)
result[i] = list[indices[i]];
return result;
}
}

8 Responses to “Combinatorics in C#”

  1. Gever says:

    Hi,
    This is beautiful example and solution, but 1 year ago I was come up against with factorial, that has been value up to max int. Therefore , current solution is suitable to the limited permutations and generic solution is using in delegates without collection results in the list. Thanks,

  2. the.source says:

    Those are really nice and useful utility functions. However, it appears to me that GetPermutations without repetition is not working correctly. When I run the following code:

    CombinatoricsUtilities.GetPermutations(new char[] { ‘a’, ‘b’, ‘c’ }, a => { Console.WriteLine(a.ToArray()); }, 2, false);

    …the output is:

    ab
    ac
    bb
    bc
    cb
    cc

    …when it should be:

    ab
    ac
    ba
    bc
    ca
    cb

  3. Noldorin says:

    You’re right. The permutations code is flawed; thanks for pointing that out. It calculates the right *number* of permutations, just not the right permutations!

    I’ll try to rewrite it at some point soon.

  4. Pama says:

    Thanks! Your GetCombinations method solved a problem i was working on. Saved me a lot of hassle.

  5. Alberto says:

    Very useful! Thank you very much!

  6. lostgdi says:

    excellent work, thank you a lot.

  7. Nishant Vashisth says:

    Thank you so much !
    your code helped me out big time with my project. It feels like this code was meant for my project.
    I even credited you in the project !

  8. Jason Law says:

    Great work!!!
    Do you already had the bug fixed for the non-repetition for permutations?

RSS feed for comments on this post. And trackBack URL.

Leave a Reply


%d bloggers like this: