Print all Possible Combinations out a List with Max Values-CodePudding

I’m having an issue with an algorithm I’m trying to implement in C# (the language doesn't matter much I guess).

Let’s say I have a list that could be of any length..for example:

var maxNumbers = new List<int>{5,3,2}();

The numbers in the list represent the maximum value of each entry. For example, the first entry means that it can be any number between 1 and 5 (5 is included).

Now, I want to print all combinations of every possible value for each entry in the list.

To explain:

The first number in the list is 5, so the possible values are 1,2,3,4,5
The second number in the list is 3, so the possible values are 1,2,3
The last number in the list is 2, so the possible values are 1,2

My algorithm should print something like:

1-1-1

1-1-2

1-2-1

1-2-2

1-3-1

1-3-2

1-2-1

etc.

I tried to implement this using recursion but wasn't able to get it. Here is my code:

    void Iterate(List<int> numbers)
{
    if (numbers.Count == 0)
    {
        Console.WriteLine("");
        return;
    }
    int number = numbers[0];
    for (int i = 1; i <= number; i  )
    {
        Console.WriteLine($"{i} ");
        Iterate(numbers.Where((v, index) => index != 0).ToList());
    }

}

Can anyone provide insights?

CodePudding user response：

A non recursive approach;

We use Select(Enumerable.Range) to turn your list of maxes into a list of list of ints representing all the numbers..

Then we repeatedly use SelectMany to add another level to the list. SelectMany expects to be fed an enumerable. In the first instance there is only one item in combos, which gets crossed with 5 items from the first entry in ints, so SelectMany produces 5 items. Second time round SelectMany effectively thinks it's expanding a "5 lists of 3 items" into a "list of 15 items". Third time round SelectMany thinks it's expanding a "15 lists of 2 items" into a "list of 30 items"...

 public static string[] Combine(IEnumerable<int> maxes)
 {
     var ints = maxes.Select(max => Enumerable.Range(1, max));
     IEnumerable<string> combos = new[] { "" };

     foreach (var i in ints)
     {
         combos = combos.SelectMany(r => i.Select(x => r   (r == "" ? "" : "-")   x));
     }

     return combos.ToArray();
 }

CodePudding user response：

This answer fixes your code, the crucial problem with which, for me, was that the solution didn't carry any memory of where it had got to so far with making the output, so there isn't any way for iterate to repeat the earlier loop outputs

Here's the fixed code:

static void Iterate(List<int> numbers, string sofar)
{
    if (numbers.Count == 0)
    {
        Console.WriteLine(sofar);
        return; 
    }
    
    for (int i = 1; i <= numbers[0]; i  )
    {
        Iterate(numbers.Skip(1).ToList(), sofar   i   " ");
    }
}

Your code in the question hs a bit of a typo in that it does a WriteLine in the for loop which really messed up the output. Removing that to just Write you get:

If I add some spaces to change the alignment:

1 1 1 
    2    --> it's 1 1 2
  2 1    --> it's 1 2 1
    2    --> it's 1 2 2 etc
  3 1 
    2 
2 1 1 
    2 
  2 1 
    2 
  3 1 
    2 
3 1 1 
    2 
  2 1 
    2 
  3 1 
    2 
...

You can see it's nearly there, in that it's printing the number that changes each time, it's just lost any memory of what to print in terms of the numbers that haven't changed. The altered code passes the "string we generated so far" and devolves responsibility for printing it to just the if. Each time the loop calls Iterate it passes the string built so far so it keeps that memory of where it got up to