using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace MoreLinq
{
public static partial class MoreEnumerable
{
///
/// Returns a sequence of representing all of the subsets
/// of any size that are part of the original sequence.
///
///
/// This operator produces all of the subsets of a given sequence. Subsets are returned
/// in increasing cardinality, starting with the empty set and terminating with the
/// entire original sequence.

/// Subsets are produced in a deferred, streaming manner; however, each subset is returned
/// as a materialized list.

/// There are 2^N subsets of a given sequence, where N => sequence.Count().
///
/// Sequence for which to produce subsets
/// The type of the elements in the sequence
/// A sequence of lists that represent the all subsets of the original sequence
/// Thrown if is
public static IEnumerable> Subsets(this IEnumerable sequence)
{
if (sequence == null)
throw new ArgumentNullException("sequence");
return SubsetsImpl(sequence);
}
///
/// Returns a sequence of representing all subsets of the
/// specified size that are part of the original sequence.
///
/// Sequence for which to produce subsets
/// The size of the subsets to produce
/// The type of the elements in the sequence
/// A sequence of lists that represents of K-sized subsets of the original sequence
///
/// Thrown if is
///
///
/// Thrown if is less than zero.
///
public static IEnumerable> Subsets(this IEnumerable sequence, int subsetSize)
{
if (sequence == null)
throw new ArgumentNullException("sequence");
if (subsetSize < 0)
throw new ArgumentOutOfRangeException("subsetSize", "Subset size must be >= 0");
// NOTE: Theres an interesting trade-off that we have to make in this operator.
// Ideally, we would throw an exception here if the {subsetSize} parameter is
// greater than the sequence length. Unforunately, determining the length of a
// sequence is not always possible without enumerating it. Herein lies the rub.
// We want Subsets() to be a deferred operation that only iterates the sequence
// when the caller is ready to consume the results. However, this forces us to
// defer the precondition check on the {subsetSize} upper bound. This can result
// in an exception that is far removed from the point of failure - an unfortunate
// and undesirable outcome.
// At the moment, this operator prioritizes deferred execution over fail-fast
// preconditions. This however, needs to be carefully considered - and perhaps
// may change after further thought and review.
return new SubsetGenerator(sequence, subsetSize);
}
///
/// Underlying implementation for Subsets() overload.
///
/// The type of the elements in the sequence
/// Sequence for which to produce subsets
/// Sequence of lists representing all subsets of a sequence
private static IEnumerable> SubsetsImpl(IEnumerable sequence)
{
var sequenceAsList = sequence.ToList();
var sequenceLength = sequenceAsList.Count;
// the first subset is the empty set
yield return new List();
// all other subsets are computed using the subset generator
// this check also resolves the case of permuting empty sets
if (sequenceLength > 0)
{
for (var i = 1; i < sequenceLength; i++)
{
// each intermediate subset is a lexographically ordered K-subset
var subsetGenerator = new SubsetGenerator(sequenceAsList, i);
foreach (var subset in subsetGenerator)
yield return subset;
}
yield return sequenceAsList; // the last subet is the original set itself
}
}
///
/// This class is responsible for producing the lexographically ordered k-subsets
///
///
private sealed class SubsetGenerator : IEnumerable>
{
#region Nested Classes
///
/// SubsetEnumerator uses a snapshot of the original sequence, and an
/// iterative, reductive swap algorithm to produce all subsets of a
/// predetermined size less than or equal to the original set size.
///
private class SubsetEnumerator : IEnumerator>
{
#region Private Fields
private readonly IList m_Set; // the original set of elements
private readonly T[] m_Subset; // the current subset to return
private readonly int[] m_Indices; // indices into the original set
// TODO: It would be desirable to give these index members clearer names
private bool m_Continue; // termination indicator, set when all subsets have been produced
private int m; // previous swap index (upper index)
private int m2; // current swap index (lower index)
private int k; // size of the subset being produced
private int n; // size of the original set (sequence)
private int z; // count of items excluded from the subet
#endregion
#region Constructors
public SubsetEnumerator(IList set, int subsetSize)
{
// precondition: subsetSize <= set.Count
if (subsetSize > set.Count)
throw new ArgumentOutOfRangeException("subsetSize", subsetSize, "Subset size must be <= sequence.Count()");
// initialize set arrays...
m_Set = set;
m_Subset = new T[subsetSize];
m_Indices = new int[subsetSize];
// initialize index counters...
Reset();
}
#endregion
#region IEnumerator Members
public void Reset()
{
m = m_Subset.Length;
m2 = -1;
k = m_Subset.Length;
n = m_Set.Count;
z = n - k + 1;
m_Continue = m_Subset.Length > 0;
}
public IList Current
{
get { return (IList)m_Subset.Clone(); }
}
object IEnumerator.Current
{
get { return Current; }
}
public bool MoveNext()
{
if (!m_Continue)
return false;
if (m2 == -1)
{
m2 = 0;
m = k;
}
else
{
if (m2 < n - m)
{
m = 0;
}
m++;
m2 = m_Indices[k - m];
}
for (var j = 1; j <= m; j++)
m_Indices[k + j - m - 1] = m2 + j;
ExtractSubset();
m_Continue = (m_Indices[0] != z);
return true;
}
void IDisposable.Dispose() { }
#endregion
#region Private Methods
private void ExtractSubset()
{
for (var i = 0; i < k; i++)
m_Subset[i] = m_Set[m_Indices[i] - 1];
}
#endregion
}
#endregion
#region Private Members
private readonly IEnumerable m_Sequence;
private readonly int m_SubsetSize;
#endregion
#region Constructors
public SubsetGenerator(IEnumerable sequence, int subsetSize)
{
if (sequence == null)
throw new ArgumentNullException("sequence");
if (subsetSize < 0)
throw new ArgumentOutOfRangeException("subsetSize", "{subsetSize} must be between 0 and set.Count()");
m_SubsetSize = subsetSize;
m_Sequence = sequence;
}
#endregion
#region Public Methods
///
/// Returns an enumerator that produces all of the k-sized
/// subsets of the initial value set. The enumerator returns
/// and for each subset.
///
/// an that enumerates all k-sized subsets
public IEnumerator> GetEnumerator()
{
return new SubsetEnumerator(m_Sequence.ToList(), m_SubsetSize);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
}
}
}