Combinations with C # repetitions
I need help with repeat combinations. Search all over the net and although I found a few examples I cannot fully understand them. My goal is simple: the (CombinationsWithRepetiion) function takes a list with elements (in this case, integers) and length (which 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 thanks you in advance!
source to share
recursion
Good,
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;
}
}
You first check for edge cases for recursion (in this case if length <= 0
) - in this case the response is an empty string (btw: I choose to return strings since you didn't say what you really need - should be easily changed).
Either way, you look at each input i
and recursivley takes the next smaller combinations and just concatenates them together (with String-concatination because I want strings).
I hope you understand the material IEnumerable
/ yield
if you don't mention it in the comments.
Here's a sample output:
foreach (var c in CombinationsWithRepition(new int[]{1,2,3}, 3))
Console.WriteLine (c);
111
112
113
...
332
333
converting numbers
Below is the idea I sketched out in the comment below and I have no problem with exceptions (recursion can be on long lengths) - this assumes strings too, since they are easier to work with (and I can make it simple PadLeft
to keep things simple )
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);
}
source to share