using System;
using System.Collections;

namespace Identifier {

    public class Combination<T> : IEnumerable, IEnumerator {

        private T[] items;
        private int atATime;
        private int current = -1;
        private long count;

        public Combination(T[] list, int n) {
            this.items = list;
            this.atATime = n;
            this.count = Choose(this.items.Length, this.atATime);
        }

        public T[] GetCombination(long n) {
            if (n >= count) {
                throw new ArgumentOutOfRangeException(String.Format("", 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;
        }

        public long NumberOfCombinations {
            get {
                return count;
            }
        }

        public T[] this[int n] {
            get {
                return GetCombination(n);
            }
        }

        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("");
            }
            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;
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return this;
        }

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

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

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