Here's a small class that can be used to generate Combinations/Permutations. 

public class Combinatorics
{
    public static IEnumerable<IEnumerable<T>> Permutations<T>(IList<T> items, int setSize)
    {
        if (setSize > 0)
            foreach (T item in items)
            {
                IList<T> remainingItems = items.Where(n => !item.Equals(n)).ToList();

                foreach (IEnumerable<T> remainingPermutations in Permutations(remainingItems, setSize - 1))
                    yield return Enumerable.Concat<T>(new T[] { item }, remainingPermutations);
            }
        else
            yield return new T[0];
    }

    public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> items, int setSize)
    {
        int[] a = new int[setSize];
        List<T> returnList = new List<T>(setSize);

        for (int i = 0; i < a.Length; i++)
            a[i] = i;

        foreach (int item in a)
            returnList.Add(items[item]);

        yield return returnList.ToArray();

        long numLeft = GetTotalNumberOfCombinations(items.Count, setSize);

        while (numLeft > 1)
        {
            int i = setSize - 1;
            while (a[i] == items.Count - setSize + i)
                i--;

            a[i] = a[i] + 1;
            for (int j = i + 1; j < setSize; j++)
                a[j] = a[i] + j - i;

            numLeft--;

            returnList.Clear();

            foreach (int item in a)
                returnList.Add(items[item]);

            yield return returnList.ToArray();

        } 
    }

    private static long GetTotalNumberOfCombinations(long itemCount, long setSize)
    {
        //takes advantage of the fact that COMBIN(100,97) == COMBIN(100,3) 
        
        if (itemCount < setSize) return 0;
        if (itemCount == setSize) return 1;

        long delta, iMax;

        delta = setSize < itemCount - setSize ? itemCount - setSize : setSize;
        iMax = setSize < itemCount - setSize ? setSize : itemCount - setSize;
        
        long returnValue = delta + 1;

        for (long i = 2; i <= iMax; ++i)
            checked { returnValue = (returnValue * (delta + i)) / i; }

        return returnValue;
    }
}

Comments


Comments are closed