I needed an algorithm that could return all combinations of k number of elements within a finite set of n elements.
Furthermore I wanted the algorithm to work in a non-recursive (iterative) way in C#.
Step forward StackOverflow, specifically this answer given by Juan Antonio Cano
I’ve taken his code and just made one or two modifications, as suggested by ReSharper.
Full code listing for the console app as shown:
Program.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Techniques
{
public static class Program
{
private static bool NextCombination(IList<int> num, int n, int k)
{
bool finished;
var changed = finished = false;
if (k <= 0) return false;
for (var i = k - 1; !finished && !changed; i--)
{
if (num[i] < n - 1 - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
for (var j = i + 1; j < k; j++)
num[j] = num[j - 1] + 1;
changed = true;
}
finished = i == 0;
}
return changed;
}
private static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
var elem = elements.ToArray();
var size = elem.Length;
if (k > size) yield break;
var numbers = new int[k];
for (var i = 0; i < k; i++)
numbers[i] = i;
do
{
yield return numbers.Select(n => elem[n]);
} while (NextCombination(numbers, size, k));
}
private static void Main()
{
const int k = 3;
var n = new[] {"1", "2", "3", "4", "5"};
Console.Write("n: " );
foreach (var item in n)
{
Console.Write("{0} ", item);
}
Console.WriteLine();
Console.WriteLine("k: {0}", k);
Console.WriteLine();
foreach (IEnumerable<string> i in Combinations(n, k))
Console.WriteLine(string.Join(" ", i));
}
}
}
So for an array of n = 5 integers {“1”, “2”, “3”, “4”, “5”} and k = 3 the program console output is as shown:
Great code! thank you!
What about if need the n to be 100…? I mean an array with many values. How can I declare the array to be from 1 to 100…
thanks again
Hello again…I manage to solve the issue with the array…
but now I need to show the results in a datagridview..with columns
such as
Number 1 | Number 2|Number 3|Number 4|Number 5
thank you
hi, i have dynamic array received from json file how to perform combination on that dynamic unknown c and r value?
Great job man. You saved me some work 🙂 Thanks