Generating All Partitions of A Set – C# Implementation
The following is the C# implementation of the Fortran algorithm posted in the previous post for generating all possible partitions of a set of items. We consider the items to be unique although they may be the same item (that is Object.Equals returns true) for one or more items in the input set. This is a straightforward implementation that uses a “lazy” enumerator. The implementation is broken into three parts: the first is the IEnumerable implementation. The second is the IEnumerator implementation. The third is the extension method that makes generating all partitions very intuitive and discoverable.
/// <summary>
/// A enumeration of all possible partitions of a set of items.
/// </summary>
/// <typeparam name="T">The type of the items in the set being partitioned.</typeparam>
public sealed class AllPartitionsEnumerable<T> : IEnumerable<IEnumerable<IEnumerable<T>>>
{
/// <summary></summary>
[DebuggerBrowsable(DebuggerBrowsableState.Collapsed)]
private IEnumerable<T> items;
/// <summary>
/// Creates and initializes an instance of the <see cref="AllPartitionsEnumerable{T}"/> type.
/// </summary>
/// <param name="items">The set of items to be partitioned.</param>
public AllPartitionsEnumerable(IEnumerable<T> items)
: base ()
{
this.items = items;
}
/// <summary>
/// Gets an enumerator to iterate over the partitions in this enumeration.
/// </summary>
/// <returns>An instance of <see cref="IEnumerator{T}"/>.</returns>
public IEnumerator<IEnumerable<IEnumerable<T>>> GetEnumerator()
{
return new AllPartitionsEnumerator<T>(this.items);
}
/// <summary>
/// Gets an enumerator to iterate over the partitions in this enumeration.
/// </summary>
/// <returns>An instance of <see cref="IEnumerator{T}"/>.</returns>
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
/// <summary>
/// An enumerator to iterate over the items in an instance of <see cref="AllPartitionsEnumerable{T}"/>.
/// </summary>
/// <typeparam name="T">The type of the items in the set being partitioned.</typeparam>
public sealed class AllPartitionsEnumerator<T> : IEnumerator<IEnumerable<IEnumerable<T>>>
{
/// <summary>The original set of items over which partitions are created.</summary>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
private T[] items;
/// <summary>Flag to indicate if this enumerator has been disposed of.</summary>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
private bool isDisposed;
/// <summary>Flag to indicate if this enumerator is in its initial state.</summary>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
private bool isFirst;
/// <summary>The number of partitions in the current selection.</summary>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
private int nc;
/// <summary>An array of values indicating the number of values in the partition at the specified index.</summary>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
private int[] p;
/// <summary>An array of indices indicating to which partition the item at the specified index belongs.</summary>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
private int[] q;
/// <summary>The current partition.</summary>
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
private T[][] current;
/// <summary>
/// Creates and initializes an instance of the <see cref="AllPartitionsEnumerator{T}"/> type.
/// </summary>
/// <param name="items">The original set of items over which partitions are enumerated.</param>
public AllPartitionsEnumerator(IEnumerable<T> items)
: base()
{
if (null == items)
{
throw new ArgumentNullException("items");
}
this.isFirst = true;
this.items = items.ToArray();
this.nc = 0;
this.p = new int[this.items.Length];
this.q = new int[this.items.Length];
this.current = null;
}
/// <summary>
/// Gets the current partition.
/// </summary>
public IEnumerable<IEnumerable<T>> Current
{
get
{
this.CheckIfDisposed();
return this.current;
}
}
/// <summary>
/// Disposes of this enumerator and releases all resources held by it.
/// </summary>
public void Dispose()
{
if (this.isDisposed)
{
return;
}
this.isDisposed = true;
this.items = null;
this.p = null;
this.q = null;
this.nc = 0;
this.current = null;
this.isFirst = true;
}
/// <summary>
/// Gets the current partition.
/// </summary>
object IEnumerator.Current
{
get
{
return this.Current;
}
}
/// <summary>
/// Selects the next item in the set of all partitions.
/// </summary>
/// <returns><c>true</c> if an item was selected; <c>false</c> if we are past the last element.</returns>
public bool MoveNext()
{
this.CheckIfDisposed();
if (this.isFirst)
{
this.isFirst = false;
this.nc = 1;
this.p[0] = this.items.Length;
for (int i = 0; i < this.items.Length; ++i)
{
this.q[i] = this.nc;
}
this.Select();
return true;
}
if (this.nc == this.items.Length )
{
return false;
}
int n = this.items.Length;
int m = n;
int l = this.q[m-1];
while (this.p[l - 1] == 1)
{
this.q[m - 1] = 1;
--m;
l = this.q[m - 1];
}
this.nc += m - n;
this.p[0] = this.p[0] + n - m;
if (l == this.nc)
{
++this.nc;
this.p[this.nc - 1] = 0;
}
this.q[m - 1] = l + 1;
this.p[l - 1] = this.p[l - 1] - 1;
this.p[l] = this.p[l] + 1;
this.Select();
return true;
}
/// <summary>
/// Resets this enumerator to its initial state.
/// </summary>
public void Reset()
{
this.CheckIfDisposed();
this.current = null;
this.isFirst = true;
this.isDisposed = false;
this.p = new int[this.items.Length];
this.q = new int[this.items.Length];
this.nc = 0;
}
/// <summary>
/// Selects the items for the current partition.
/// </summary>
private void Select()
{
this.current = new T[this.nc][];
for (int i = 0; i < this.nc; ++i)
{
int k = 0;
this.current[i] = new T[this.p[i]];
for (int j = 0; j < this.items.Length; ++j)
{
if (this.q[j] == i + 1)
{
this.current[i][k] = this.items[j];
++k;
}
}
}
}
/// <summary>
/// Checks and throws an exception if this enumerator has been disposed.
/// </summary>
private void CheckIfDisposed()
{
if (this.isDisposed)
{
throw new ObjectDisposedException(this.GetType().FullName);
}
}
}
/// <summary>
/// Retrieves all possible partitions of a set of items.
/// </summary>
/// <typeparam name="T">The type of the items in the original set.</typeparam>
/// <param name="items">The original set of items over which partitions are created.</param>
/// <returns>All possible partitions of the items in <paramref name="items"/>.</returns>
public static IEnumerable<IEnumerable<IEnumerable<T>>> AllPartitions<T>(this IEnumerable<T> items)
{
return new AllPartitionsEnumerable<T>(items);
}
That’s all there is to it. A simple program that generates the 52 partitions of the set {1, 2, 3, 4, 5} is given below:
var intset = 1.To(5);
var parts = intset.AllPartitions();
int j = 1;
foreach (var part in parts)
{
var list = part.ToList();
Console.Write((j++) + " - ");
Console.Write(list[0].ToCsvString());
for (int i = 1; i < list.Count; ++i)
{
Console.Write(" : ");
Console.Write(list[i].ToCsvString());
}
Console.WriteLine();
}
Have fun.
Please note: I hope to make the two implementations posted here as well a few others related to simple combinatorial objects available as an open source library on CodePlex
Technorati Tags: c#,partitions,algorithm,combinatorial,combinatorics
. I will post details when this is done.