Combinations With Repetitions C#

问题:

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!

回答1:

recursion

Ok,

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

static IEnumerable<String> CombinationsWithRepition(IEnumerable<int> input, int length)
{
    if (length <= 0)
        yield return "";
    else
    {
        foreach(var i in input)
            foreach(var c in CombinationsWithRepition(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 CombinationsWithRepition(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> CombinationsWithRepition(string symbols, int len)
{
    for (var i = 0; i < Math.Pow(symbols.Length,len); i++)
        yield return Convert (symbols, i, len);
}

回答2:

 string[] items = {"1", "2", "3"};

var query = from i1 in items
            from i2 in items
            from i3 in items

            select i1 + i2 + i3 ;


foreach(var result in query)
    Console.WriteLine(result);
            Console.ReadKey();