Combination Generation

Momerath 2 Tallied Votes 1K Views Share

As a companion article to my Permutation Generation, I now present Combination generation.

This snippet will do a lazy generation of the combinations of a set of objects. Each combination has a grouping size (number of items in each combination). If you need a different grouping size, you'll have to create a new instance.

As was done in the permutation class, you can request specific lexical combinations either by calling the method GetCombination or by using the index operator.

How to use:
First you'll need an array of object. Call the Combination constructor passing the array and the grouping size. Since this is a generic class, you'll have to provide the class type of the array (like all generics).

The test example will take an array of six strings, with a grouping size of 3, and:

  • Display how many different combinations there are.
  • Display all the combinations.
  • Display the fourth lexical combination using a method call.
  • Display the sixth lexical combination using indexing.
using System;
using System.Text;
using Whittle.Math;

namespace Whittle {
    class Program {
        static void Main(string[] args) {
            int counter = 0;
            String[] myItems = { "A", "B", "C", "D", "E", "F" };
            Combination<string> myCombos = new Combination<string>(myItems, 3);

            Console.WriteLine("For {0} items there are {1} combinations", myItems.Length, myCombos.NumberOfCombinations);
            Console.WriteLine();
            foreach (String[] perm in myCombos) {
                Console.Write("{0} ", SeqFormat(perm));
                counter = (counter + 1) % 6;
                if (counter == 0) Console.WriteLine();
            }
            Console.WriteLine();
            Console.WriteLine("The fourth lexical combination is {0}", SeqFormat(myCombos.GetCombination(4)));
            Console.WriteLine();
            Console.WriteLine("The sixth lexical combination is {0}", SeqFormat(myCombos[6]));

            Console.ReadLine();
        }

        static String SeqFormat(String[] strings) {
            StringBuilder sb = new StringBuilder();
            sb.Append("[");
            foreach (String s in strings) {
                sb.Append(s);
            }
            sb.Append("]");

            return sb.ToString();
        }
    }
}

How it works:
The wikipedia article explains it better than I ever could :)

Limitations:
Because this requires the use of factorials (even though they are generated in a unique way) it is possible to overflow the int variables used to generate the combinations. If you really need larger combinations, try changing all the int values to long, or BigInteger.

Acknowlegments:
As before, my sources are wikipedia and the 2006 MSDN Article "Test Run" by Dr. James McCaffrey.

ddanbe commented: The master did it again! +8
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
    }
}
codeholic -1 Newbie Poster
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.