3

I'm trying to write an algorithm, and due to my lack of experience writing complex algorithms, I'm struggling a bit here. So, in this scenario I have n number of character arrays, each array containing m characters. I need to generate every possible combination of characters between the arrays.

Example, I have the following arrays:

arr1 = [2, 3]
arr2 = ['y', 1]
arr3 = [1]
arr4 = [2, 'u', 4]

With the above arrays all of the possible combinations are:

2y12
2y1u
2y14
2112
211u
2114
3y12
3y1u
3y14
3112
311u
3114

There can be any number n arrays, and any number of characters in each array. So this algorithm needs to scale. I was thinking that a recursive solution might be possible, I just can't wrap my head around how that would work. This problem is very similar to the post Generating all Possible Combinations, except I still don't see how to make the solution dynamic in order to handle any number of arrays with any number of elements within said arrays.

My solution will end up being written in C#, but you can help my with any other language or pseudo code.

John Seed
  • 357
  • 1
  • 7
  • 18
  • 1
    Possible duplicate of https://stackoverflow.com/q/3093622 – Jesin Nov 16 '17 at 03:10
  • @Jesin, its a very similar situation to that question. That doesn't help me see how to make the algorithm dynamic in order to handle any number of arrays with any number of elements within them. – John Seed Nov 16 '17 at 03:14
  • @cheesebal35 perhaps https://stackoverflow.com/q/13647662 then? – Jesin Nov 16 '17 at 03:40
  • Check my answer and see if it helps. https://stackoverflow.com/a/46314165/3575018 – thebenman Nov 16 '17 at 04:54

1 Answers1

6
void Dodge(List<List<T>> domains)
{
    Fuski(domains, new List<T>());
}

void Fuski(List<List<T>> domains, List<T> vector)
{
    if (domains.Count == vector.Count)
    {
        Console.WriteLine(string.Join("", vector)); 
        return;
    }
    foreach (var value in domains[vector.Count])
    {
        var newVector = vector.ToList();
        newVector.Add(value);
        Fuski(domains, newVector);
    }
}
Optional Option
  • 1,521
  • 13
  • 33
  • u-oh woow, tha's a great solution, thanks a lot for sharing! just replace predicate with string that is better to get to work the Join method :) – Fabio Guerrazzi Apr 28 '19 at 15:25