0

Suppose you have an unbound list of named arrays:

ArrayNode[] vertexes = new ArrayNode[] {
    new ArrayNode("nouns", new String[]{"John", "Mary"}),
    new ArrayNode("verbs", new String[]{"Eats", "Works", "Plays"}),
    new ArrayNode("objects", new String[]{"Food", "Computer", "Guitar"})
 };

Given an order to follow, say "nouns->verbs->objects", what algorithm can we use to associate all elements of the arrays in the given order? The output is something like the following:

["John Eats Food"], ["John Eats Computer"], ["John Eats Guitar"], 
["John Works Food"], ["John Works Computer"], ["John Works Guitar"], 
..., ..., ..., 
...,                 ["Mary Plays Computer"], ["Mary Plays Guitar"]

The number of arrays is unbound and the sequence can be any for the given number of arrays.

Solution

Using Java 8 and Google Guava 19 Lists.cartesianProduct Take a look at the answer to this at Iterative Cartesian Product in Java

Community
  • 1
  • 1
Marcello DeSales
  • 21,361
  • 14
  • 77
  • 80
  • 1
    I'm trying to go with a mix of DFS and BFS... Not sure if that's the right approach... – Marcello DeSales May 27 '16 at 17:07
  • I'm looking for a Java implementation... But yea, do you have reference to a simple backtracking example? – Marcello DeSales May 27 '16 at 17:16
  • The link provided in the comment by Oriol has a few good implementations that you could port to Java. See especially [this functional one](http://stackoverflow.com/a/36234242/539048) and [this recursive one](http://stackoverflow.com/a/29585704/539048). – GreenGiant May 27 '16 at 17:25
  • 1
    I implemented using Google Guava's List.cartesianProduct method. Thanks! – Marcello DeSales May 27 '16 at 19:03

1 Answers1

0

You could traverse the arrays in inorder fashion to get the output in the desired order.

Sumit Jha
  • 2,095
  • 2
  • 21
  • 36