Combinations With Repetitions C#

Question

I need assistance with Combinations with Repetition. Have searched all over the net and although I found a few examples I can't understand them completely. My goal is simple a function (CombinationsWithRepetiion) receives list with items (in this case integer values) and length (that represents how long each combination can be) and returns a list containing the result.

    List<int> input = new List<int>() {1, 2, 3}
    CombinationsWithRepetition(input, length);

result:

length = 1: 1, 2, 3

length = 2: 11,12,13,21,22,23,31,32,33

length = 3: 111,112 ....

I hope someone helps me and thank you in advance!

Answer 1

recursion

Ok,

here is the C# version - I walk you through it

static IEnumerable<String> CombinationsWithRepetition(IEnumerable<int> input, int length)
{
    if (length <= 0)
        yield return "";
    else
    {
        foreach(var i in input)
            foreach(var c in CombinationsWithRepetition(input, length-1))
                yield return i.ToString() + c;
    }
}

First you check the border-cases for the recursion (in this case if length <= 0) - in this case the answer is the empty string (btw: I choose to return strings as you did not say what your really needed - should be easy to change).

In any other case you look at each input i and recursivley take the next-smaller combinations and just plug em together (with String-concatination because I wanted strings).

I hope you understand the IEnumerable/yield stuff - if not say so in the comments please.

Here is a sample output:

foreach (var c in CombinationsWithRepetition(new int[]{1,2,3}, 3))
    Console.WriteLine (c);
111
112
113
...
332
333

converting numbers

The following uses the idea I sketched in the comment below and has no problems with stack-overflow exceptions (recursion might for big lenght) - this too assumes strings as they are easier to work with (and I can do a simple PadLeft to simplify things)

static String Convert(string symbols, int number, int totalLen)
{
    var result = "";
    var len = symbols.Length;
    var nullSym = symbols [0];
    while (number > 0)
    {
        var index = number % len;
        number = number / len;
        result = symbols [index] + result;
    }
    return result.PadLeft (totalLen, nullSym);
}

static IEnumerable<String> CombinationsWithRepetition(string symbols, int len)
{
    for (var i = 0; i < Math.Pow(symbols.Length,len); i++)
        yield return Convert (symbols, i, len);
}