Iterative implementation of K of N variations

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

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]

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

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).

StackExchange Code Review Q#144006, answer score: 2