CODEWITHSUNDEEP
arraysalgorithmsorting
Tactical Downvote
Tactical Downvote

Reputation: 2393

How to find all combinations of items of multiple arrays

Lets say these are the start arrays:

[a,b,c]
[d]
[e,f]

What algorithm could produce the following arrays?

[a,d,e]
[a,d,f]
[b,d,e]
[b,d,f]
[c,d,e]
[c,d,f]

The number of start arrays can vary.

Upvotes: 1

Views: 1176

Answers (5)

isaac.hazan
isaac.hazan

Reputation: 3874

The proposed solution above has a big problem in the sense the developer needs to know the number of arrays ahead and create the number of loops accordingly.

The following solution in C# does it dynamically based on the number of arrays that you actually have and it's type agnostic:

    static void Main(string[] args)
    {
        List<List<char>> masterListChar = new List<List<char>>();
        List<char> c1 = new List<char>() { 'a', 'b', 'c' };
        List<char> c2 = new List<char>() { 'd' };
        List<char> c3 = new List<char>() { 'e', 'f'};
        masterListChar.Add(c1);
        masterListChar.Add(c2);
        masterListChar.Add(c3);

        //PrintCombinations(masterListInt);
        PrintCombinations(masterListChar);
        Console.ReadKey();
    }

    public static void PrintCombinations<T>(List<List<T>> masterArray)
    {
        T[] combination = new T[masterArray.Count];
        WalkOnSubArray(combination, masterArray, 0);
    }

    public static void WalkOnSubArray<T>(T[] combination, List<List<T>> masterArray, int masterIndex)
    {
        List<T> currentArray = masterArray[masterIndex];
        for (int i = 0; i < currentArray.Count; ++i)
        {
            combination[masterIndex] = currentArray[i];

            if(masterIndex != masterArray.Count - 1)
                WalkOnSubArray(combination, masterArray, masterIndex + 1);
            else
                Console.WriteLine(String.Join(",", combination));
        }
    }

Upvotes: 0

Egor Skriptunoff
Egor Skriptunoff

Reputation: 23727

Let there are k arrays of n1, n2... nk elements respectively.
Writing all combinations is very like to writing all numbers in mixed radix.
So, simply loop over all possible numbers from 0 to (n1n2...nk-1) and write it down in mixed radix representation with "digits" taken from your arrays - only two nested loops are required.

Upvotes: 0

Alberto Bonsanto
Alberto Bonsanto

Reputation: 18022

Another method is a graphical one, you start with the originals sets and you move their content clockwise and store the combinations. Example first rotate the last row, and after the last rotation move the last - 1 row (in this case d, but you can't rotate it) so you will rotate the first row. It's like the binary sum.

[a,b,c]     [a,b,c]---->[b,c,a]     [b,c,a]---->[c,a,b]     [c,a,b]              
[d]         [d]         [d]         [d]         [d]         [d]    
[e,f]------>[f,e]------>[e,f]------>[f,e]------>[e,f]------>[f,e]

PD: you will only save the first elements of each array always.

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

The simplest algorithm you can think of is the best you can have. As the answer is of size the multiplied dimensions of all the arrays not much of an improvement can be made here. I personally recommend using recursion as the number of arrays can not be too big without making the number of resulting arrays really huge.

Upvotes: 1

Sorceror
Sorceror

Reputation: 4843

Depends on language, but formally something like this (when you have 3 arrays as you specified)

for el1 in first_array do
  for el2 in second_array do
    for el3 in third_array do
      begin
        create new element in result array as [e1, el2, el3]
      end

Upvotes: 3

Related Questions