Combinatorics.cs

// <copyright file="Combinatorics.cs" company="Math.NET">
// Math.NET Numerics, part of the Math.NET Project
// http://numerics.mathdotnet.com
// http://github.com/mathnet/mathnet-numerics
//
// Copyright (c) 2009-2015 Math.NET
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
// </copyright>

using System;
using System.Collections.Generic;
using System.Linq;
using MathNet.Numerics.Properties;
using MathNet.Numerics.Random;

namespace MathNet.Numerics
{
    /// <summary>
    /// Enumerative Combinatorics and Counting.
    /// </summary>
    public static class Combinatorics
    {
        /// <summary>
        /// Count the number of possible variations without repetition.
        /// The order matters and each object can be chosen only once.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Each element is chosen at most once.</param>
        /// <returns>Maximum number of distinct variations.</returns>
        public static double Variations(int n, int k)
        {
            if (k < 0 || n < 0 || k > n)
            {
                return 0;
            }

            return Math.Floor(
                0.5 + Math.Exp(
                    SpecialFunctions.FactorialLn(n)
                    - SpecialFunctions.FactorialLn(n - k)));
        }

        /// <summary>
        /// Count the number of possible variations with repetition.
        /// The order matters and each object can be chosen more than once.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Each element is chosen 0, 1 or multiple times.</param>
        /// <returns>Maximum number of distinct variations with repetition.</returns>
        public static double VariationsWithRepetition(int n, int k)
        {
            if (k < 0 || n < 0)
            {
                return 0;
            }

            return Math.Pow(n, k);
        }

        /// <summary>
        /// Count the number of possible combinations without repetition.
        /// The order does not matter and each object can be chosen only once.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Each element is chosen at most once.</param>
        /// <returns>Maximum number of combinations.</returns>
        public static double Combinations(int n, int k)
        {
            return SpecialFunctions.Binomial(n, k);
        }

        /// <summary>
        /// Count the number of possible combinations with repetition.
        /// The order does not matter and an object can be chosen more than once.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Each element is chosen 0, 1 or multiple times.</param>
        /// <returns>Maximum number of combinations with repetition.</returns>
        public static double CombinationsWithRepetition(int n, int k)
        {
            if (k < 0 || n < 0 || (n == 0 && k > 0))
            {
                return 0;
            }

            if (n == 0 && k == 0)
            {
                return 1;
            }

            return Math.Floor(
                0.5 + Math.Exp(
                    SpecialFunctions.FactorialLn(n + k - 1)
                    - SpecialFunctions.FactorialLn(k)
                    - SpecialFunctions.FactorialLn(n - 1)));
        }

        /// <summary>
        /// Count the number of possible permutations (without repetition).
        /// </summary>
        /// <param name="n">Number of (distinguishable) elements in the set.</param>
        /// <returns>Maximum number of permutations without repetition.</returns>
        public static double Permutations(int n)
        {
            return SpecialFunctions.Factorial(n);
        }

        /// <summary>
        /// Generate a random permutation, without repetition, by generating the index numbers 0 to N-1 and shuffle them randomly.
        /// Implemented using Fisher-Yates Shuffling.
        /// </summary>
        /// <returns>An array of length <c>N</c> that contains (in any order) the integers of the interval <c>[0, N)</c>.</returns>
        /// <param name="n">Number of (distinguishable) elements in the set.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        public static int[] GeneratePermutation(int n, System.Random randomSource = null)
        {
            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);

            int[] indices = new int[n];
            for (int i = 0; i < indices.Length; i++)
            {
                indices[i] = i;
            }

            SelectPermutationInplace(indices, randomSource);
            return indices;
        }

        /// <summary>
        /// Inverts a permutation, returning a new permutation.
        /// No checks are performed to validate the input (apart from null checks).
        /// </summary>
        /// <param name="permutation">Permutation to invert.</param>
        /// <returns>The inverted permutation.</returns>
        public static int[] InvertPermutation(int[] permutation)
        {
            if (permutation == null) throw new ArgumentNullException(nameof(permutation));
            var result = Enumerable.Range(0, permutation.Length).ToArray();
            Sorting.Sort(permutation, result);
            return result;
        }

        /// <summary>
        /// Lazily generates all permutations lexicographically.
        /// Note that the same array is yielded on each iteration,
        /// so care is needed when converting to a collection.
        /// </summary>
        /// <param name="n">Number of (distinguishable) elements in the set.</param>
        /// <returns>A lazy enumeration of all unique permutations of the set.</returns>
        public static IEnumerable<int[]> GenerateAllPermutations(int n)
        {
            // This method follows Algorithm L found in
            // Knuth, "Combinatorial Algorithms" The Art of Computer Science vol. 4A, 7.2.1.2

            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);

            // We'll repeatedly yield the following array as we generate the permutations.
            // The first entry is just the items in lexicographical order.
            var a = Enumerable.Range(0, n).ToArray();
            int j, l, swap;
            while (true)
            {
                yield return a;
                j = n - 1;
                // Following Knuth's notation, the entry a_j is found at position a[j-1].
                while (j > 0 && a[j - 1] >= a[j])
                    j--;
                if (j == 0) break; // Terminates the algorithm.
                l = n;
                while (a[j - 1] >= a[l - 1])
                    l--;
                // Swap aj and al
                swap = a[j - 1];
                a[j - 1] = a[l - 1];
                a[l - 1] = swap;
                Array.Reverse(a, j, n - j);
            }
        }

        /// <summary>
        /// Lazily generates all combinations lexicographically.
        /// Note that the same array is yielded on each iteration,
        /// so care is needed when converting to a collection.
        /// </summary>
        /// <param name="n">Number of items in the set.</param>
        /// <param name="k">Number of items to choose, without replacement.</param>
        /// <returns>A lazy enumeration of all unique subsets of size k.</returns>
        public static IEnumerable<int[]> GenerateAllCombinations(int n, int k)
        {
            // This method follows Algorithm T found in
            // Knuth, "Combinatorial Algorithms," The Art of Computer Science vol. 4A, 7.2.1.3

            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);
            if (k < 0) throw new ArgumentOutOfRangeException(nameof(k), Resources.ArgumentNotNegative);

            // We'll repeatedly yield the following array as we generate the permutations.
            // The first entry is just the items in lexicographical order.
            var a = new int[k];

            var c = Enumerable.Range(0, k + 2).ToArray();
            c[k] = n;
            c[k + 1] = 0;

            int x;
            int j = k;
            if (k <= n) // Returns empty enumerable if k > n;
            {
                if (k == n)
                    yield return c.Take(k).ToArray();
                else
                    while (true)
                    {
                        for (int i = 0; i < k; i++)
                            a[i] = c[i];
                        yield return a;

                        if (j > 0)
                        {
                            x = j;
                        }
                        else
                        {
                            // Easy case?
                            if (c[0] + 1 < c[1])
                            {
                                c[0] = c[0] + 1;
                                continue;
                            }

                            // We differ slightly here from Knuth.
                            // Instead of j=2, we set to 1.
                            // But we put j++ at the beginning of the do loop that immediately follows.
                            j = 1;

                            do
                            {
                                j++;
                                c[j - 2] = j - 2;
                                x = c[j - 1] + 1;
                            } while (x == c[j]);

                            if (j > k) break;
                        }


                        c[j - 1] = x;
                        j--;
                    }
            }
        }

        /// <summary>
        /// Select a random permutation, without repetition, from a data array by reordering the provided array in-place.
        /// Implemented using Fisher-Yates Shuffling. The provided data array will be modified.
        /// </summary>
        /// <param name="data">The data array to be reordered. The array will be modified by this routine.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        public static void SelectPermutationInplace<T>(T[] data, System.Random randomSource = null)
        {
            var random = randomSource ?? SystemRandomSource.Default;

            // Fisher-Yates Shuffling
            for (int i = data.Length - 1; i > 0; i--)
            {
                int swapIndex = random.Next(i + 1);
                T swap = data[i];
                data[i] = data[swapIndex];
                data[swapIndex] = swap;
            }
        }

        /// <summary>
        /// Select a random permutation from a data sequence by returning the provided data in random order.
        /// Implemented using Fisher-Yates Shuffling.
        /// </summary>
        /// <param name="data">The data elements to be reordered.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        public static IEnumerable<T> SelectPermutation<T>(this IEnumerable<T> data, System.Random randomSource = null)
        {
            var random = randomSource ?? SystemRandomSource.Default;
            T[] array = data.ToArray();

            // Fisher-Yates Shuffling
            for (int i = array.Length - 1; i >= 0; i--)
            {
                int k = random.Next(i + 1);
                yield return array[k];
                array[k] = array[i];
            }
        }

        /// <summary>
        /// Generate a random combination, without repetition, by randomly selecting some of N elements.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>Boolean mask array of length <c>N</c>, for each item true if it is selected.</returns>
        public static bool[] GenerateCombination(int n, System.Random randomSource = null)
        {
            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);

            var random = randomSource ?? SystemRandomSource.Default;

            bool[] mask = new bool[n];
            for (int i = 0; i < mask.Length; i++)
            {
                mask[i] = random.NextBoolean();
            }

            return mask;
        }

        /// <summary>
        /// Generate a random combination, without repetition, by randomly selecting k of N elements.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Each element is chosen at most once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>Boolean mask array of length <c>N</c>, for each item true if it is selected.</returns>
        public static bool[] GenerateCombination(int n, int k, System.Random randomSource = null)
        {
            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);
            if (k < 0) throw new ArgumentOutOfRangeException(nameof(k), Resources.ArgumentNotNegative);
            if (k > n) throw new ArgumentOutOfRangeException(nameof(k), string.Format(Resources.ArgumentOutOfRangeSmallerEqual, "k", "n"));

            var random = randomSource ?? SystemRandomSource.Default;

            bool[] mask = new bool[n];
            if (k*3 < n)
            {
                // just pick and try
                int selectionCount = 0;
                while (selectionCount < k)
                {
                    int index = random.Next(n);
                    if (!mask[index])
                    {
                        mask[index] = true;
                        selectionCount++;
                    }
                }

                return mask;
            }

            // based on permutation
            int[] permutation = GeneratePermutation(n, random);
            for (int i = 0; i < k; i++)
            {
                mask[permutation[i]] = true;
            }

            return mask;
        }

        /// <summary>
        /// Select a random combination, without repetition, from a data sequence by selecting k elements in original order.
        /// </summary>
        /// <param name="data">The data source to choose from.</param>
        /// <param name="elementsToChoose">Number of elements (k) to choose from the data set. Each element is chosen at most once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>The chosen combination, in the original order.</returns>
        public static IEnumerable<T> SelectCombination<T>(this IEnumerable<T> data, int elementsToChoose, System.Random randomSource = null)
        {
            T[] array = data as T[] ?? data.ToArray();

            if (elementsToChoose < 0) throw new ArgumentOutOfRangeException(nameof(elementsToChoose), Resources.ArgumentNotNegative);
            if (elementsToChoose > array.Length) throw new ArgumentOutOfRangeException(nameof(elementsToChoose), string.Format(Resources.ArgumentOutOfRangeSmallerEqual, "elementsToChoose", "data.Count"));

            bool[] mask = GenerateCombination(array.Length, elementsToChoose, randomSource);

            for (int i = 0; i < mask.Length; i++)
            {
                if (mask[i])
                {
                    yield return array[i];
                }
            }
        }

        /// <summary>
        /// Generates a random combination, with repetition, by randomly selecting k of N elements.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Elements can be chosen more than once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>Integer mask array of length <c>N</c>, for each item the number of times it was selected.</returns>
        public static int[] GenerateCombinationWithRepetition(int n, int k, System.Random randomSource = null)
        {
            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);
            if (k < 0) throw new ArgumentOutOfRangeException(nameof(k), Resources.ArgumentNotNegative);

            var random = randomSource ?? SystemRandomSource.Default;

            int[] mask = new int[n];
            for (int i = 0; i < k; i++)
            {
                mask[random.Next(n)]++;
            }

            return mask;
        }

        /// <summary>
        /// Select a random combination, with repetition, from a data sequence by selecting k elements in original order.
        /// </summary>
        /// <param name="data">The data source to choose from.</param>
        /// <param name="elementsToChoose">Number of elements (k) to choose from the data set. Elements can be chosen more than once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>The chosen combination with repetition, in the original order.</returns>
        public static IEnumerable<T> SelectCombinationWithRepetition<T>(this IEnumerable<T> data, int elementsToChoose, System.Random randomSource = null)
        {
            if (elementsToChoose < 0) throw new ArgumentOutOfRangeException(nameof(elementsToChoose), Resources.ArgumentNotNegative);

            T[] array = data as T[] ?? data.ToArray();
            int[] mask = GenerateCombinationWithRepetition(array.Length, elementsToChoose, randomSource);

            for (int i = 0; i < mask.Length; i++)
            {
                for (int j = 0; j < mask[i]; j++)
                {
                    yield return array[i];
                }
            }
        }

        /// <summary>
        /// Generate a random variation, without repetition, by randomly selecting k of n elements with order.
        /// Implemented using partial Fisher-Yates Shuffling.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Each element is chosen at most once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>An array of length <c>K</c> that contains the indices of the selections as integers of the interval <c>[0, N)</c>.</returns>
        public static int[] GenerateVariation(int n, int k, System.Random randomSource = null)
        {
            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);
            if (k < 0) throw new ArgumentOutOfRangeException(nameof(k), Resources.ArgumentNotNegative);
            if (k > n) throw new ArgumentOutOfRangeException(nameof(k), string.Format(Resources.ArgumentOutOfRangeSmallerEqual, "k", "n"));

            var random = randomSource ?? SystemRandomSource.Default;

            int[] indices = new int[n];
            for (int i = 0; i < indices.Length; i++)
            {
                indices[i] = i;
            }

            // Partial Fisher-Yates Shuffling
            int[] selection = new int[k];
            for (int i = 0, j = indices.Length - 1; i < selection.Length; i++, j--)
            {
                int swapIndex = random.Next(j + 1);
                selection[i] = indices[swapIndex];
                indices[swapIndex] = indices[j];
            }

            return selection;
        }

        /// <summary>
        /// Select a random variation, without repetition, from a data sequence by randomly selecting k elements in random order.
        /// Implemented using partial Fisher-Yates Shuffling.
        /// </summary>
        /// <param name="data">The data source to choose from.</param>
        /// <param name="elementsToChoose">Number of elements (k) to choose from the set. Each element is chosen at most once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>The chosen variation, in random order.</returns>
        public static IEnumerable<T> SelectVariation<T>(this IEnumerable<T> data, int elementsToChoose, System.Random randomSource = null)
        {
            var random = randomSource ?? SystemRandomSource.Default;
            T[] array = data.ToArray();

            if (elementsToChoose < 0) throw new ArgumentOutOfRangeException(nameof(elementsToChoose), Resources.ArgumentNotNegative);
            if (elementsToChoose > array.Length) throw new ArgumentOutOfRangeException(nameof(elementsToChoose), string.Format(Resources.ArgumentOutOfRangeSmallerEqual, "elementsToChoose", "data.Count"));

            // Partial Fisher-Yates Shuffling
            for (int i = array.Length - 1; i >= array.Length - elementsToChoose; i--)
            {
                int swapIndex = random.Next(i + 1);
                yield return array[swapIndex];
                array[swapIndex] = array[i];
            }
        }

        /// <summary>
        /// Generate a random variation, with repetition, by randomly selecting k of n elements with order.
        /// </summary>
        /// <param name="n">Number of elements in the set.</param>
        /// <param name="k">Number of elements to choose from the set. Elements can be chosen more than once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>An array of length <c>K</c> that contains the indices of the selections as integers of the interval <c>[0, N)</c>.</returns>
        public static int[] GenerateVariationWithRepetition(int n, int k, System.Random randomSource = null)
        {
            if (n < 0) throw new ArgumentOutOfRangeException(nameof(n), Resources.ArgumentNotNegative);
            if (k < 0) throw new ArgumentOutOfRangeException(nameof(k), Resources.ArgumentNotNegative);

            var random = randomSource ?? SystemRandomSource.Default;

            int[] ret = new int[k];
            random.NextInt32s(ret, 0, n);
            return ret;
        }

        /// <summary>
        /// Select a random variation, with repetition, from a data sequence by randomly selecting k elements in random order.
        /// </summary>
        /// <param name="data">The data source to choose from.</param>
        /// <param name="elementsToChoose">Number of elements (k) to choose from the data set. Elements can be chosen more than once.</param>
        /// <param name="randomSource">The random number generator to use. Optional; the default random source will be used if null.</param>
        /// <returns>The chosen variation with repetition, in random order.</returns>
        public static IEnumerable<T> SelectVariationWithRepetition<T>(this IEnumerable<T> data, int elementsToChoose, System.Random randomSource = null)
        {
            if (elementsToChoose < 0) throw new ArgumentOutOfRangeException(nameof(elementsToChoose), Resources.ArgumentNotNegative);

            T[] array = data as T[] ?? data.ToArray();
            int[] indices = GenerateVariationWithRepetition(array.Length, elementsToChoose, randomSource);

            for (int i = 0; i < indices.Length; i++)
            {
                yield return array[indices[i]];
            }
        }
    }
}