generate all k-combinations of n numbers[1, 2, ..., n]

using System;
using System.Collections.Generic;

namespace _21.GenerateCombinations
{
    class Program
    {
        static void Main(string[] args)
        {
            //Same as commented input code below
            int n;
            int k;
            InputNAndK(out n, out k);

            //You can use "#region" to hide blocks of code or comments.
            #region
            /*
            Console.Write("Enter n: ");
            int n = int.Parse(Console.ReadLine());

            Console.Write("Enter k: ");
            int k = int.Parse(Console.ReadLine());
            */
            #endregion

            if (n <= 0)
            {
                Console.WriteLine("n must be bigger than 0");
                return;
            }

            if (n < 0 || k < 0)
            {
                Console.WriteLine("Both n and k must be greater than 0,");
                return;
            }

            if (n < k)
            {
                Console.WriteLine("n must be bigger than k");
                return;
            }

            //Note: new List<int>(n) means list with CAPACITY of n; its actual count is still 0.
            //So you can`t have method of the type "InitializeList(list);" but you can have
            //method of the type "InitializeArray( combination);",
            //where combination is array of some size.
            List<int> list = new List<int>(n);
            InitializeList(list, n);

            int[] combination = new int[k];
            InitializeArray(combination);

            bool nextCombinationExists = true;
            //Returns all combinations without repetitions
            do
            {
                PrintCombination(combination);
                nextCombinationExists = NextIndexCombination(list.Count, k, combination);

            } while (nextCombinationExists);
        }

        private static void InputNAndK(out int n, out int k)
        {
            Console.Write("Enter n: ");
            n = int.Parse(Console.ReadLine());

            Console.Write("Enter k: ");
            k = int.Parse(Console.ReadLine());
        }

        private static void InitializeList(List<int> list, int count)
        {
            for (int i = 1; i <= count; i++)
            {
                list.Add(i);
            }
        }

        private static void PrintCombination(int[] comb)
        {
            for (int i = 0; i < comb.Length; i++)
            {
                Console.Write((comb[i] + 1) + " ");
            }
            Console.WriteLine();
        }

        //Explanation of the method.
        #region
        /*The method generates next k-combination of indexes without repetition,
          for given n, k and current combination of indexes.

         *The logic behind the method:
          1. The idea of int[] arrayOfIndexes is to represent indexes in another array. After changing
          values in arrayOfIndexes, we can access the values in the other array:

          arrayOfIndexes = {0, 1, 2} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, b, c
          arrayOfIndexes = {0, 1, 3} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, b, d
          arrayOfIndexes = {0, 1, 4} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, b, e
          arrayOfIndexes = {0, 2, 3} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, c, d
          ..................................................................................

          NOTE: in case of otherArray of type {1, 2, 3, .... n} arrayOfIndexes[i] + 1 == otherArray[i]

          2. int[] arrayOfIndexes is a reference type - that means that the method modifies it.
          See: http://pastebin.com/R6kbsqJw

          3. See http://en.wikipedia.org/wiki/File:Combinations_without_repetition;_5_choose_3.svg
         We have combinations of 5 items taken 3 at a time, without repetition

          What happens in the picture:
                1. The last item increases by one until it reaches its max value - the max
                value of the last item is 5.
                2. Then, the next item makes the same thing, only its max value is 5 - 1.
                3. The the next - with max value 5 - 2. And so on...
                ....................
                ....................
                So, there is a max value that each item has to reach before the next item is changed.
                Max value formula: maxIndex - (kClass - 1 - currentIndex), where
                    - maxIndex = n - 1, where n - the count of all items
                    - kClass = k,  the class of the combination
                    - currentIndex - the index of the current item in arrayOfIndexes.

         How the algoritm works:

         foreach item in arrayOfIndexes(but starting from the last and going to the first) we check
         if this item has not reached its max value
               - if it hasn`t:
                       1. get index of that item (itemIndex = currentIndex;)
                       2. arrayOfIndexes[itemIndex]++;
                       3. every nextItem = previous item + 1
                       4. return true (combinationExists)
               - if it has:
                       1. check next item while find such that hasn`t or iterate through all items.

         If all items have reached its max value. "itemIndex" remains equal to "kClass".
         In that case no more combinations exist.
         */
        #endregion
        static bool NextIndexCombination(int elementsCount, int kClass, int[] arrayOfIndexes)
        {
            int maxIndex = elementsCount - 1;
            // Find the first item that has not reached its maximum value.
            int itemIndex = kClass;
            for (int currentIndex = arrayOfIndexes.Length - 1; currentIndex >= 0; currentIndex--)
            {
                if (arrayOfIndexes[currentIndex] < maxIndex - (kClass - 1 - currentIndex))
                {
                    itemIndex = currentIndex;
                    break;
                }
            }

            // No more combinations to be generated. Every index has reached its
            // maximum value.
            if (itemIndex == kClass)
            {
                return false;
            }
            // Genereate the next combination in lexographical order.
            arrayOfIndexes[itemIndex]++;
            for (int i = itemIndex + 1; i < arrayOfIndexes.Length; i++)
            {
                arrayOfIndexes[i] = arrayOfIndexes[i - 1] + 1;
            }

            return true;
        }

        static void InitializeArray(int[] combination)
        {
            for (int i = 0; i < combination.Length; i++)
            {
                combination[i] = i;
            }
        }
    }
}