Skip to content

Instantly share code, notes, and snippets.

@pgsin pgsin/Combinations.cs
Last active Jun 18, 2018

Embed
What would you like to do?
using System;
namespace CombinatoricsLib
{
public class Combinations
{
private static ulong Factorial(int x, int until = 0)
{
ulong res = 1;
while (x != until)
{
res *= (ulong)x--;
}
return res;
}
public static int Combination0(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
return (int)(Factorial(n) / (Factorial(k) * Factorial(n - k)));
}
public static int Combination1(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
return (int)(Factorial(n, n - k) / Factorial(k));
}
public static int Combination2(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
int[] triangle = new int[k + 1];
triangle[0] = 1;
// expanding
int i = 0;
for (; i < k; i++)
{
for (int j = i + 1; j > 0; j--)
{
triangle[j] += triangle[j - 1];
}
}
// progressing
for (; i < n - k; i++)
{
for (int j = k; j > 0; j--)
{
triangle[j] += triangle[j - 1];
}
}
// collapsing
for (; i < n; i++)
{
int until = k - (n - i);
for (int j = k; j > until; j--)
{
triangle[j] += triangle[j - 1];
}
}
return triangle[k];
}
public static int Combination3(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
int count = n;
int x = 1;
while (x < k)
{
count *= n - x++;
count /= x;
}
return count;
}
public static int CombinationHansen(int k, int n)
{
k = Math.Min(k, n - k);
if (n < 2 || k < 1) return 1;
if (k == 1) return n;
int count = n;
for (int x = 1; x <= k - 1; x++)
{
count = count * (n - x) / x;
}
return (count / k);
}
}
}
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Attributes.Columns;
using BenchmarkDotNet.Attributes.Exporters;
using BenchmarkDotNet.Attributes.Jobs;
using BenchmarkDotNet.Reports;
using BenchmarkDotNet.Running;
using CombinatoricsLib;
namespace Benchmarks
{
[ClrJob]
[RPlotExporter, RankColumn]
public class CombinationsBenchmark
{
[Params(8, 11, 16, 19, 20)] public int N;
[Benchmark]
public void Combination0()
{
for (int i = 0; i <= N; i++)
{
Combinations.Combination0(i, N);
}
}
[Benchmark]
public void Combination1()
{
for (int i = 0; i <= N; i++)
{
Combinations.Combination1(i, N);
}
}
[Benchmark]
public void Combination2()
{
for (int i = 0; i <= N; i++)
{
Combinations.Combination2(i, N);
}
}
[Benchmark]
public void Combination3()
{
for (int i = 0; i <= N; i++)
{
Combinations.Combination3(i, N);
}
}
[Benchmark]
public void CombinationHansen()
{
for (int i = 0; i <= N; i++)
{
Combinations.CombinationHansen(i, N);
}
}
public static Summary Run()
{
return BenchmarkRunner.Run<CombinationsBenchmark>();
}
}
}
BenchmarkDotNet=v0.10.14, OS=Windows 10.0.16299.371 (1709/FallCreatorsUpdate/Redstone3)
Intel Core i7-7820HQ CPU 2.90GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores
Frequency=2835938 Hz, Resolution=352.6170 ns, Timer=TSC
  [Host] : .NET Framework 4.7.1 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
  Clr    : .NET Framework 4.7.1 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0

Job=Clr  Runtime=Clr  
Method N Mean Error StdDev Median Rank
Combination0 8 98.27 ns 1.5877 ns 1.3258 ns 98.36 ns 6
Combination1 8 74.25 ns 0.9599 ns 0.8979 ns 74.20 ns 4
Combination2 8 118.75 ns 0.6953 ns 0.6504 ns 118.68 ns 7
Combination3 8 38.15 ns 0.2153 ns 0.1909 ns 38.13 ns 1
CombinationHansen 8 50.54 ns 0.6765 ns 0.6328 ns 50.56 ns 2
Combination0 11 177.24 ns 2.1238 ns 1.9866 ns 177.43 ns 9
Combination1 11 121.65 ns 1.5122 ns 1.4145 ns 122.21 ns 8
Combination2 11 270.98 ns 5.3618 ns 10.0707 ns 266.82 ns 13
Combination3 11 72.61 ns 0.8160 ns 0.7633 ns 72.83 ns 3
CombinationHansen 11 95.04 ns 0.6758 ns 0.5643 ns 94.99 ns 5
Combination0 16 357.80 ns 3.3599 ns 3.1429 ns 357.29 ns 18
Combination1 16 211.48 ns 1.1436 ns 1.0697 ns 211.45 ns 11
Combination2 16 707.82 ns 9.0663 ns 8.4806 ns 710.00 ns 22
Combination3 16 180.39 ns 1.8440 ns 1.7249 ns 180.69 ns 10
CombinationHansen 16 222.64 ns 1.5143 ns 1.2645 ns 222.95 ns 12
Combination0 19 495.49 ns 3.0490 ns 2.5461 ns 495.04 ns 20
Combination1 19 277.37 ns 5.7925 ns 13.3093 ns 273.31 ns 14
Combination2 19 1,181.08 ns 7.1716 ns 6.3574 ns 1,180.61 ns 23
Combination3 19 275.50 ns 1.2740 ns 1.1917 ns 275.46 ns 14
CombinationHansen 19 329.21 ns 4.2598 ns 3.9847 ns 328.31 ns 17
Combination0 20 539.65 ns 2.1774 ns 2.0367 ns 539.69 ns 21
Combination1 20 288.70 ns 3.8677 ns 3.6178 ns 288.69 ns 15
Combination2 20 1,381.07 ns 10.9915 ns 9.1784 ns 1,378.39 ns 24
Combination3 20 314.97 ns 1.5115 ns 1.4139 ns 315.18 ns 16
CombinationHansen 20 373.35 ns 4.7866 ns 4.4774 ns 375.16 ns 19
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.