Obtaining combinations of k elements from n in C#

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:

Leave a Reply