Instantly share code, notes, and snippets.

# ZodmanPerth/Binomials.cs

Last active August 28, 2021 09:56
k-combination Algorithms of Rank and Unrank for Computer Programmers. Blog post at http://www.redperegrine.net/2021/04/10/software-algorithms-for-k-combinations/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 namespace System { /// Mathematical functions for binomials public static class Binomials { // / \ // | n | from n // | | // | k | choose k // \ / // Kudos: https://en.wikipedia.org/wiki/Combination#Example_of_counting_combinations /// Calculates the Binomial Coefficient (n choose k), which is the number of unique k-sized combinations in a set of n elements. /// We divide before multiplying to minimise the chance of overflow. public static int CalculateBinomialCoefficient(int n, int k) { if (k > n) return 0; if (k == n) return 1; double result = n; // n choose 1 for (double i = 1; i < k; i++) { var numerator = n - i; double factor = numerator / (i + 1); result *= factor; } return (int)result; } //// Extensions /// Returns the number (n) choose k public static int Choose(this int n, int k) => CalculateBinomialCoefficient(n, k); /// Calculates the number of unique combinations of size k from n numbers (k-combination) public static int CountUniqueCombinationsOfSize(this int n, int k) => CalculateBinomialCoefficient(n, k); } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 using System; namespace LG.App.Services.Combinations { /// A 1-based Combinatorial Number System of n numbers with unique k-combinations. /// The code here is optimised for use. Mathematical comprehension is obscured by the optimisations. public class FastCombinatorialNumberSystem : ICombinatorialNumberSystem { readonly int n, k; readonly int _dualOfZero; // dual of the number 0 in a zero based system /// Creates a combinatorial number system with unique k-combinations chosen from n items public FastCombinatorialNumberSystem(int n, int k) { if (n <= 0) throw new ArgumentOutOfRangeException(nameof(n)); if (k <= 0) throw new ArgumentOutOfRangeException(nameof(k)); this.n = n; this.k = k; _dualOfZero = n - 1; } public int Rank(int[] combination) { int ci; var dual = n.Choose(k); // Add 1 (for base 1) var reducingK = k; for (int i = 0; i < k; i++) { // Map to combinadic and take 1 (for base 0) ci = _dualOfZero - combination[i] + 1; // removed brackets, turning - to + // Remove ci portion of the dualOfCombinadic from dual (diminish) dual -= ci.Choose(reducingK); reducingK--; } return dual; } public int[] Unrank(int rank) { // Calculate the dual (moving to zero based) var dual = n.Choose(k) - rank; var combination = new int[k]; var diminishingRank = dual; var reducingK = k; for (int i = 0; i < k; i++) { // Calculate ci of the combinadic of the dual var ci = CalculateLargestRankBelowThreshold(n, reducingK, diminishingRank); diminishingRank -= ci.Choose(reducingK); reducingK--; // Map to zero-based combination and add 1 (for base 1) combination[i] = _dualOfZero - ci + 1; } return combination; } /// Local Functions /// Returns the highest rank of n choose k that is less than max int CalculateLargestRankBelowThreshold(int n, int k, int threshold) { int i = n - 1; while (i.Choose(k) > threshold) i--; return i; } } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 naming file
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 using BenchmarkDotNet.Running; using PerformanceTests.CombinatorialNumberSystems; namespace LG.Benchmark.Tests { public class Program { // NOTE: // This follows the strategy for testing with BenchmarkDotNet laid down by Adam Sitnik here: // https://github.com/dotnet/BenchmarkDotNet/issues/1460#issuecomment-646531625 // // Build in release mode. // Run from command line from within the project test folder with: // dotnet run -c Release public static void Main(string[] args) { //var summary = BenchmarkRunner.Run(typeof(RankTests)); var summary = BenchmarkRunner.Run(typeof(UnRankTests)); } } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 using BenchmarkDotNet.Attributes; using LG.App.Services.Combinations; using System.Collections.Generic; namespace PerformanceTests.CombinatorialNumberSystems { [MemoryDiagnoser] public class RankTests { /// Test data for benchmark tests. The first digit is N, the second is K. public IEnumerable KCombinations() { yield return new object[] { 5, 3, new[] { 1, 3, 5 } }; yield return new object[] { 45, 6, new[] { 11, 16, 23, 34, 42, 43 } }; yield return new object[] { 100, 6, new [] { 11, 16, 23, 34, 42, 43 } }; } [Benchmark(Baseline = true)] [ArgumentsSource(nameof(KCombinations))] public int Rank(int n, int k, int[] kCombination) { var cns = new CombinatorialNumberSystem(n, k); return cns.Rank(kCombination); } [Benchmark] [ArgumentsSource(nameof(KCombinations))] public int FastRank(int n, int k, int[] kCombination) { var fastCns = new FastCombinatorialNumberSystem(n, k); return fastCns.Rank(kCombination); } } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters