using System;

namespace Chapter10Exercise2
{
    class KofNCombinationsIterative
    {
     static int[] combination;
     //------------------------------------------------------------------------- 

        static void Main(string[] args)
        {
            Console.WriteLine("Type n:");
            int n = int.Parse(Console.ReadLine());

            Console.WriteLine("Type k:");
            int k = int.Parse(Console.ReadLine());

            FindCombinations(n, k);
        }
        //---------------------------------------------------------------------- 

        /*
            Method: FindCombinations(int n, int k)

            It prints the combinations of k elements
            in a set of n elements.

            It increments the values of an array of size k
            from 1 to n, starting from the last element.
        */
        private static void FindCombinations(int n, int k)
        {
            combination = new int[k];
            int initialValue = 1;
            InitializeArray(combination, initialValue);
            int valueAfterOverflow = 1;

            while (true)
            {
                // print current combination
                PrintCombination();

                // increase value at current index
                int index = k - 1;
                ++combination[index];

                // go to the next index  
                while (combination[index] > n)
                {
                    ++valueAfterOverflow;
                    combination[index] = valueAfterOverflow;
                    --index;

                    // if current index is < 0 exit
                    if (index < 0)
                    {
                        return;
                    }
                    ++combination[index];
                }
            }
        }
        //---------------------------------------------------------------------- 

        /*
            Method: PrintCombination()

        */
        private static void PrintCombination()
        {
            Console.Write("(");
            for (int i = 0; i < combination.Length; ++i)
            {
                Console.Write(combination[i]);

                if (i < combination.Length - 1)
                {
                    Console.Write(", ");
                }
            }
            Console.WriteLine(")");
        }
        //---------------------------------------------------------------------- 

        /*
            Method: InitializeArray(int[] arr, int initialValue)
            
        */
        static void InitializeArray(int[] arr, int initialValue)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = initialValue;
            }
        }
    }
}