Iterative implementation of K of N variations

Question

Objective:

Print all combinations with repetition of k elements out of a set of n elements.

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;
            }
        }
    }
}

Input:

Type n:
3
Type к:
2

Output:

(1 1), (1 2), (1 3), (2 2), (2 3), (3 3)

---

I've been trying to get rid of the variable valueAfterOverlow to no avail, is there a way to use some of the already defined variables: index, n and k to update the value after overflow?

Is the complexity: $$O(n^k)$$ ,i.e. n-incrementations of k variables (plus some additional work)?

Is there more effective iterative algorithm?

Answer 1

Your code is wrong: if I test it with n=3, k=3 I get

(1 1 1), (1 1 2), (1 1 3), (1 2 2), (1 2 3), (1 3 3), (2 5 4), (3 7 6)

However, you're on the right lines. Assuming that you want (or at least don't mind) to return each combination in ascending order, the way that I find intuitive to think about it is as a set of k nested loops:

for (combination[0] = 1; combination[0] <= n; combination[0]++)
    for (combination[1] = combination[0]; combination[1] <= n; combination[1]++)
        ...
            for (combination[k] = combination[k-1]; combination[k] <= n; combination[k]++)
                PrintCombination(combination);

To turn that into an iterative approach, you count but when you overflow then instead of resetting to 0 you reset to the final value which doesn't overflow. I agree with Kore's now deleted answer that you should use Enumerable.Repeat to initialise, and I also think you should make the generation method generate rather than print, so it comes down to

    private static IEnumerable<int[]> FindCombinations(int n, int k)
    {
        var combination = Enumerable.Repeat(1, k).ToArray();
        while (true)
        {
            // generate current combination
            yield return (int[])combination.Clone();

            // find index which isn't going to overflow
            int index = k - 1;
            while (combination[index] == n)
            {
                if (--index < 0) yield break;
            }

            // increment and fill right
            for (int finalDigit = combination[index] + 1; index < n; index++)
            {
                combination[index] = finalDigit;
            }
        }
    }

The performance is O(n) per combination returned, and that is optimal (just cloning the answer to return it is already O(n), and even if we don't clone and guarantee elsewhere that we won't modify the array, we'll still surely want to use it).