Skip to content

Instantly share code, notes, and snippets.

@mlaily
Last active August 27, 2017 21:20
Show Gist options
  • Save mlaily/afe6a9047eef174da6440eb43c6c055a to your computer and use it in GitHub Desktop.
Save mlaily/afe6a9047eef174da6440eb43c6c055a to your computer and use it in GitHub Desktop.
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp
{
    public static class Combinations
    {
        public static IEnumerable<IReadOnlyList<T>> GetAllCombinations<T>(IEnumerable<T> set, int combinationLength)
            => GetAllCombinationsUsingOnlyOneInstance(set, combinationLength).Select(x => x.ToArray());
        public static IEnumerable<string> GetAllCombinations(IEnumerable<char> set, int combinationLength)
            => GetAllCombinationsUsingOnlyOneInstance_Implementation(set is char[] asArray ? asArray : set.ToArray(), combinationLength)
                .Select(result => new string(result));
        /// <summary>
        /// Warning: this method returns an <see cref="IEnumerable{T}"/>
        /// yielding always the same mutated instance of <see cref="IReadOnlyList{T}"/> multiple times.
        /// </summary>
        public static IEnumerable<IReadOnlyList<T>> GetAllCombinationsUsingOnlyOneInstance<T>(IEnumerable<T> set, int combinationLength)
            => GetAllCombinationsUsingOnlyOneInstance_Implementation(set is T[] asArray ? asArray : set.ToArray(), combinationLength);
        /// <summary>
        /// Warning: this method returns an <see cref="IEnumerable{T}"/>
        /// yielding always the same mutated instance of <see cref="IReadOnlyList{T}"/> multiple times.
        /// </summary>
        public static IEnumerable<IReadOnlyList<T>> GetAllCombinationsUsingOnlyOneInstance<T>(T[] set, int combinationLength)
            => GetAllCombinationsUsingOnlyOneInstance_Implementation(set, combinationLength);
        /// <summary>
        /// Warning: this method returns an <see cref="IEnumerable{T}"/>
        /// yielding always the same mutated instance of <typeparamref name="T"/>[] multiple times.
        /// </summary>
        private static IEnumerable<T[]> GetAllCombinationsUsingOnlyOneInstance_Implementation<T>(T[] set, int combinationLength)
        {
            var currentResult = new T[combinationLength];
            IEnumerable<T[]> GetAllCombinationsRec(int resultIndex, int remainingRecursions)
            {
                if (remainingRecursions == 0)
                {
                    yield return currentResult;
                    yield break;
                }
                for (int i = 0; i < set.Length; i++)
                {
                    currentResult[resultIndex] = set[i];
                    foreach (var item in GetAllCombinationsRec(resultIndex + 1, remainingRecursions - 1))
                    {
                        yield return item;
                    }
                }
            }
            return GetAllCombinationsRec(0, combinationLength);
        }
    }
    [MemoryDiagnoser]
    public class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<Program>();
        }
        [Benchmark(Baseline = true)]
        public object MutableCombinationsOfSixDigits()
            => Combinations.GetAllCombinationsUsingOnlyOneInstance(new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, 6).ToList();
        [Benchmark]
        public object MutableWordsOfSixDigits()
            => Combinations.GetAllCombinationsUsingOnlyOneInstance("0123456789", 6).ToList();
        [Benchmark]
        public object CombinationsOfSixDigits()
            => Combinations.GetAllCombinations(new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, 6).ToList();
        [Benchmark]
        public object WordsOfSixDigits()
            => Combinations.GetAllCombinations("0123456789", 6).ToList();
        /*
         * BenchmarkDotNet=v0.10.9, OS=Windows 10 Redstone 2 (10.0.15063)
         * BenchmarkDotNet=v0.10.9, OS=Windows 10 Redstone 2 (10.0.15063)
         * Processor=Intel Core i5-4690K CPU 3.50GHz (Haswell), ProcessorCount=4
         * Frequency=3417963 Hz, Resolution=292.5719 ns, Timer=TSC
         * .NET Core SDK=2.0.0
         *   [Host]     : .NET Core 2.0.0 (Framework 4.6.00001.0), 64bit RyuJIT
         *   DefaultJob : .NET Core 2.0.0 (Framework 4.6.00001.0), 64bit RyuJIT
         * 
         *  |                         Method |     Mean |     Error |    StdDev | Scaled | ScaledSD |      Gen 0 |     Gen 1 |     Gen 2 | Allocated |
         *  |------------------------------- |---------:|----------:|----------:|-------:|---------:|-----------:|----------:|----------:|----------:|
         *  | MutableCombinationsOfSixDigits | 117.6 ms | 0.1569 ms | 0.1390 ms |   1.00 |     0.00 | 26375.0000 | 1937.5000 |  937.5000 |  92.29 MB |
         *  |        MutableWordsOfSixDigits | 116.1 ms | 0.1854 ms | 0.1735 ms |   0.99 |     0.00 | 26375.0000 | 1937.5000 |  937.5000 |  92.29 MB |
         *  |        CombinationsOfSixDigits | 469.5 ms | 1.9253 ms | 1.8009 ms |   3.99 |     0.02 | 22300.0000 | 7262.5000 | 1933.3333 | 138.07 MB |
         *  |               WordsOfSixDigits | 372.9 ms | 3.4907 ms | 3.2652 ms |   3.17 |     0.03 | 20704.1667 | 6683.3333 | 1645.8333 | 130.44 MB |
         */
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment