Combination Generation

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
    }
}