How to generate Combinations without repetition interatively in C#

// n = 5
// k = 3
// 1, 2, 3
// 1, 2, 4
// 1, 2, 5
// 1, 3, 4
// 1, 3, 5
// 1, 4, 5
// 2, 3, 4
// 2, 3, 5
// 2, 4, 5
// 3, 4, 5

using System;
using System.Collections.Generic;

public static class GenerateCombinationsIteratively
{

    static void Main()
    {
        Console.Write("n = ");
        var n = int.Parse(Console.ReadLine());

        Console.Write("k = ");
        var k = int.Parse(Console.ReadLine());

        foreach (var combo in Combinations(k, n))
        {
            Console.WriteLine(string.Join(", ", combo));
        }
    }

    private static IEnumerable<int[]> Combinations(int k, int n)
    {
        var result = new int[k];
        var stack = new Stack<int>();
        stack.Push(1);

        while (stack.Count > 0)
        {
            var index = stack.Count - 1;
            var value = stack.Pop();

            while (value <= n)
            {
                result[index++] = value++;
                stack.Push(value);
                if (index == k)
                {
                    yield return result;
                    break;
                }
            }
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *