10

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!

user3218608
  • 133
  • 1
  • 5
  • I honestly don't know why this got downvoted - anyway the answer is not that complicated but I think it might be some sort of homework, therefore what have you tried so far? **HINT** things like this gets really easy if you think recursivley (assume you have your combinations for length (n-1) - how could you get all for length n from this? – Random Dev Sep 13 '14 at 15:18
  • Assuming it got downvoted because OP has not shown any indication that he has worked on his code at all, he has just said "gimme code pls", essentially – Dan Sep 13 '14 at 15:22
  • 2
    He didn't ask for code. .. he asked for assistance. And be real... everyone comes here hoping for code. – tronious Sep 13 '14 at 15:23
  • Its my second time asking question and didn't know that I should place my code. I have trouble wrapping my head around how to make it recursively. I'll figure it out. Thank you guys anyway! – user3218608 Sep 13 '14 at 15:26
  • well here is the basic algorithm in math (ok it's haskell): `let comb (input, len) = if len == 0 then [""] else [ show i ++ c | i <- input, c <- comb (input, len-1) ]` I think you can see what's going on even if you don't know Haskell - read the "[ ... | i <- ...]" stuff as you would read a math-set definition ;) – Random Dev Sep 13 '14 at 15:33
  • You might want to look at this library: https://linqlib.codeplex.com/ The Combinatorics class contains extension methods for generating Combinations or Permutations, allowing for repetitions if you want and specification of the sizes you want back – pinkfloydx33 Sep 13 '14 at 16:06
  • 2
    These are not combinations, these are permutations. – Dmitry Avtonomov Mar 17 '19 at 16:14

2 Answers2

17

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);
}
AdrianoRR
  • 1,131
  • 1
  • 17
  • 36
Random Dev
  • 51,810
  • 9
  • 92
  • 119
  • 2
    BTW: another way to do this (without recursion) is to *just* count up numbers and encode these numbers using the `input` as the symbols of a counting-system (for decimal we use `0`,`1`, ... `9` - for binary just `0,1`, etc,) - if you know how to do this (basically it's just div/mod) you can do this in an easy loop – Random Dev Sep 13 '14 at 15:45
  • 1
    This also works using strings (if anyone is interested in producing strings such as aaa aab abc aba, etc). Simply change the datatypes. – Hanlet Escaño Apr 16 '15 at 18:29
  • 1
    Word of caution. I'm getting "out of memory" after consuming 6GB in 2 minutes working on an array of size 3 and a length of 20. It works great for small samples, but not so much as the problem gets larger. – Kevingy Apr 15 '20 at 20:02
1
 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();
Dilip kumar
  • 11
  • 2
  • 1
    While this code may answer the question, providing additional context regarding why and/or how this code answers the question improves its long-term value. – Alex Riabov Sep 14 '18 at 13:21