1

I'm working on this algorithm exercice from GeeksForGeeks:

Given a list of arrays (of any size, not limited to two arrays), find all combinations where each combination contains one element from each given array.

Examples:

Input:

[[1, 2], [3, 4]]

Output:

1 3
1 4
2 3
2 4

I tried to resolve it myself using this approach:

Initialize "result" list of arraylist.
For each element of the first array in the input list:
   depth = 1
   while(depth < list.size())
    arrayToCombineWithItsElmt = list.get(depth)
    for(int i = 0; i < arrayToCombineWithItsElmt.size(); i++)
      GenerateCombinations(result, arrayToCombineWithItsElmt(i))
    depth++
return result

generateCombinations(List<ArrayList> result, int element) method should:

  1. copy result list (which contains previous combinations)
  2. remove all elements of result list
  3. iterate over the copied list and for each Array add the element
  4. Add the array to result list.

I didn't code (using Java) it as I felt that it's not correct (very complex way to solve). From this brute force algorithm that I got after trying to resolve an example manually, how to optimize?

SarahData
  • 769
  • 1
  • 12
  • 38
  • 1
    Isn't it just using two nested loops? – UninformedUser Oct 20 '17 at 11:31
  • @AKSW: Only if it is allways two arrays. If the number of arrays is random you would need another solution like a recursive function. – OH GOD SPIDERS Oct 20 '17 at 11:40
  • I know that it's only for two arrays, I just saw the example – UninformedUser Oct 20 '17 at 11:41
  • You can use recursion or an iterator based approach to solve it. – UninformedUser Oct 20 '17 at 11:43
  • But this question has already been answered here, thus, it's a duplicate: https://stackoverflow.com/questions/17192796/generate-all-combinations-from-multiple-lists – UninformedUser Oct 20 '17 at 11:44
  • 4
    Possible duplicate of [Generate all combinations from multiple lists](https://stackoverflow.com/questions/17192796/generate-all-combinations-from-multiple-lists) – UninformedUser Oct 20 '17 at 11:44
  • @AKSW no it's not a duplicate, that one is using Strings and I checked answers and couldn't figure out exactly.. that helped me go with the approach I proposed here and I'm looking for a solution with consideration of my approach. – SarahData Oct 20 '17 at 11:50
  • 1
    It doesn't matter of which type the elements are ... and the solution with the iterators works on generic types, thus, also works for numbers ... – UninformedUser Oct 20 '17 at 12:00
  • Ok. If someone didn't understand the solutions, what should him do? thank you. – SarahData Oct 20 '17 at 12:02
  • I edited the question @AKSW. I'm not looking for codes like mentioned as duplicate. I want to achieve requested output starting from the approach I've taken. – SarahData Oct 20 '17 at 12:10

0 Answers0