5
\$\begingroup\$

I have written this Java snippet to generate all permutations of a given Array of a HashMap. Can this be done in a better way? This algorithm is taking too much time.

What I have currently done:

Take the first element of the first array of the first HashMap, move to the next HashMap, take the first element of his array and move to next. Do this until all the elements are covered.

Data elements:

[
  {
    values=[
      2016/4/2,
      1999/1/1,
      1971/8/24,
      1967/1/1,
      1966/8/16
    ],
    columnname=age
  },
  {
    values=[
      Male,
      Female,
      other,

    ],
    columnname=gender
  }
]

Note:

  • The above example is generated by the code itself, so suggestions on changing this data format is welcomed.
  • This has just two HashMaps with few items in the array. It may have M HashMaps with N Array elements.

Code:

// `possibilities_list` has the above  mentioned `arraylist`   

final static ArrayList < HashMap < String, Object >> possibilities_list = new ArrayList < HashMap < String, Object >> (); // prodChange
static List < List < String >> final_scenarios = new ArrayList < List < String >> (); // prodChange;

public static void main(String[] args) {

    Dao dao = new Dao();
    try {
        JSONObject filters = new JSONObject(); // this will be coming from user, just used this for testing purpose.
        filters.put("e&m", "");
        filters.put("icd9", "");
        filters.put("icd10", "");
        filters.put("cpt", "");
        filters.put("dx", false);
        filters.put("rx", false);
        filters.put("procedure", false);
        filters.put("lab", false);
        filters.put("sd", false);
        filters.put("bp", false);
        filters.put("ht", false);
        filters.put("wt", false);
        filters.put("hr", false);
        filters.put("bmi", false);
        filters.put("ps", false);
        filters.put("di", false);
        filters.put("structureddata", true);

        dao.generatePossibilites(filters); // output of this is the above generated list which is stored under possibilities_list 

        @SuppressWarnings("unchecked")
        ArrayList < Object > list = (ArrayList < Object > ) possibilities_list.get(0).get("values");
        for (Object obj: list) {
            Dao.generateScenarios(possibilities_list.get(1), 1, obj + " , ");
        }
    }
}

private static void generateScenarios(HashMap < String, Object > map, int current_index, String scenarios_string) {

    // System.out.println(" map " + map);
    // System.out.println(" curreny_index " + current_index );
    // System.out.println(" scenarios_string " + scenarios_string);
    @SuppressWarnings("unchecked")
    ArrayList < Object > list = (ArrayList < Object > ) map.get("values");
    for (Object obj: list) {
        if (current_index == possibilities_list.size() - 1) {
            StringBuilder str = new StringBuilder();
            str.append(scenarios_string);
            str.append(obj);
            str.append(" , ");
            final_scenarios.add(Arrays.asList(str.toString().split(" , ")));

        } else {
            Dao.generateScenarios(possibilities_list.get(current_index + 1), ++current_index,
                scenarios_string + obj + " , ");
            current_index--;
        }
    }

}
  • I'm trying to get all permutations of the arrays of values key mentioned in above data elements example.
  • Desired output of ArrayList:

    [  
        [2016/4/2,Male],  
        [2016/4/2,Female],  
        [2016/4/2,other],  
        [2016/4/2, ],  
        [1999/1/1,Male],  
        [1999/1/1,Female],  
        [1999/1/1,other],  
        [1999/1/1, ],  
        [1971/8/24,Male],  
        [1971/8/24,Female],  
        [1971/8/24,other],  
        [1971/8/24, ],  
        [1967/1/1,Male],  
        [1967/1/1,Female],  
        [1967/1/1,other],  
        [1967/1/1, ],  
        [1966/8/16,Male],  
        [1966/8/16,Female],  
        [1966/8/16,other],  
        [1966/8/16, ]  
    ]
    

As you can see, this is the Cartesian product of the two values arrays given in the input (data elements above).

  • Problem: As you might notice, the generateScenarios method is able to create the desired List of combinations. However, on increasing the size of arrays of values key, Java throws an out-of-memory exception. I need a better way to solve the problem.
\$\endgroup\$
  • \$\begingroup\$ Do you run out of memory for the given small example? Or, it works for this small example, but doesn't work for a much larger input. Please clarify. \$\endgroup\$ – janos Jul 11 '17 at 12:00
  • \$\begingroup\$ Yes that is correct. It works for small input but runs out of memory for much larger input. Just to add, I was able to create a list of size 327000. \$\endgroup\$ – Bhavik Patel Jul 11 '17 at 12:04
1
\$\begingroup\$

After a lot of brain storming, came up with an idea.

Currently the algorithm takes each element of first array moves to next array, takes the first element and moves to next until it's the last array. When it is last array in the list, for each of the traversed elements it creates a permutation. Example : If we have 3 arrays (1,2,3),(a,b,c) and (x,y,z) . (1,a,x) is created first , (1,a,y) is next, (1,a,z),(1,b,x),(1,b,y) and so on.

But if one would notice, the 9 combinations of 2nd and 3rd array are same for all elements of first array. Meaning, for each in (1,2,3) all 9 combinations of 2nd and 3rd array would be same, hence once we have those 9 combinations we don't need to create it again for other elements of 1st array. Base on this logic the below algorithm was developed.

Performance update : When the same inputs were used for the new algorithm, I had the output in 3 secs.

Below is the code :

@SuppressWarnings("unchecked")
private static ArrayList < Object > getAllPerm(HashMap < String, Object > map, int index) {
    if (index == possibilities_list.size() - 1) {

        return (ArrayList < Object > ) map.get("values");

    } else {

        ArrayList < Object > current_list = getAllPerm(possibilities_list.get(index + 1), ++index);
        ArrayList < Object > final_list = new ArrayList < Object > ();
        for (Object currentItem: current_list) {
            for (Object currentObject: (ArrayList < Object > ) map.get("values")) {
                if (currentItem.getClass().getName().equalsIgnoreCase("java.lang.String")) {
                    final_list.add(currentObject + "," + currentItem);
                } else {
                    final_list.addAll((Collection << ? extends Object > ) currentItem);
                    final_list.add(currentObject);
                }


            }
        }

        return final_list;
    }


}
\$\endgroup\$
0
\$\begingroup\$

[Implemented as in the question,] This algorithm is taking too much time.
[with] increasing size of arrays of [choices], Java throws [OutOfMemoryError]
What exactly shall Generating the Cartesian product of N-arrays mean?
If it is providing a list of comma-separated representations of all combinations of choices given as a two-dimensional assortment of values, it is not building all such representations and adding them to a List.

  • (doc-)comment your code
  • naming: possibilities_list leaks implementation detail into a name - if not for telling conceptually like objects from each other that differ only there, prefer possibilities or choices.
  • program "against" interfaces, not classes:
    Map <String, Object> map,
    List <Object> currentDimension,
    List <Object> getAllPerm(…)

Extension to more/a variable number of "dimensions" should be evident:

/** Presents all combinations of specified <em>choices</em> as a
 *  <code>List</code> of <code>String</code>s */
public class Cartesian extends java.util.AbstractList {
    Object[][] choices;

    public Cartesian(Object[][] choices) {
        this.choices = choices;
    }

    @Override
    public Object get(int index) {
        return choices[1][index / choices[3].length]
            + ", " + choices[3][index % choices[3].length];
    }
    @Override
    public int size() {
        return choices[1].length * choices[3].length;
    }

    public static void main(String[] args) {
        System.out.println(new Cartesian( new Object[][] {
            { "bdate" }, {
                "2016/4/2",
                "1999/1/1",
                "1971/8/24",
                "1967/1/1",
                "1966/8/16"
            }, { "gender" }, {
                "Male", "Female", "other", ""
            }}));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.