Java Combinations of elements of Map>

Question

(ps. I just rewrote the question as I thought it was dealing with permutations, but it is actually dealing with combinations.)

Consider more specifically a Map<String, List<WordGroupAndScore> baseMap, with:

private static class WordGroupAndScore {
    public final WordGroup wordGroup;
    public final int score;

    public WordGroupAndScore(final WordGroup wordGroup, final int score) {
        this.wordGroup = wordGroup;
        this.score = score;
    }
}

The baseMap.size() is variable, meaning that there can be any number of Strings in the map. Also for every element in baseMap, baseMap.get(i).size() is variable. But the baseMap cannot contain empty lists.

Now I am trying to find all possible combinations. The code itself is for checking data in invoices, not always all data is available on an invoice, hence the variable amount of baseMap.size(). And the list per element in baseMap is variable, because the amount of data found depends on which invoice it is.

(Example data does not correspond one to one in the example, as in reality it is WordGroupAndScore, but I'll use Strings or BigDecimals to represent the data in the example)

Example data of baseMap (values and key pairs) strictly (A and List<B> pairs):

• ("invoiceNumber", ["0001", "0002"])
• ("invoiceDate", ["2013-10-07"])
• ("priceExclVAT, [new BigDecimal("10.00")])
• ("highVAT, [new BigDecimal("2.10")])
• ("priceInclVAT, [new BigDecimal("12.10"), new BigDecimal("14.10")])

I want to generate all possible combinations of the data.

Example output, one ("first") combination (values and single key pairs) strictly (A and B pairs):

• ("invoiceNumber", "0001")
• ("invoiceDate", "2013-10-07"])
• ("priceExclVAT, new BigDecimal("10.00"))
• ("highVAT, new BigDecimal("2.10"))
• ("priceInclVAT, new BigDecimal("12.10"))

Example output, one ("last") combination (values and single key pairs) strictly (A and B pairs):

• ("invoiceNumber", "0002")
• ("invoiceDate", "2013-10-07")
• ("priceExclVAT, new BigDecimal("10.00"))
• ("highVAT, new BigDecimal("2.10"))
• ("priceInclVAT, new BigDecimal("14.10"))

So somehow I need to iterate over the full baseMap, remember/create all combinations based on every baseMap.get(i).size(), but I am pretty much lost where to start. Biggest problem is that: how would I remember the combinations, because my baseMap is of variable size. If it would not have been variable, then I could've done it much easier.

I hope the question is clear enough.

EDIT: Added one of my tries, which doesn't work.

//Assumes that wordGroupsAndScores does not get changed during the process
private void processWordGroupAndScores(TemplateBean template) {
    System.out.println();
    System.out.println("--wordGroupsAndScores--");
    for (Map.Entry<String, List<WordGroupAndScore>> entry : wordGroupsAndScores.entrySet()) {
        System.out.println("Attribute = " + entry.getKey());
        for (WordGroupAndScore wordGroupAndScore : entry.getValue()) {
            System.out.println("WordGroupAndScore = " + wordGroupAndScore);
        }
        System.out.println(";");
    }
    System.out.println();
    //create all possible unfinishedinvoices from wordgroupandscores
    int[] indices = new int[wordGroupsAndScores.keySet().size()];
    for (int index = 0; index < indices.length; index++) {
        indices[index] = 0;
    }
    String[] keyLocation = new String[wordGroupsAndScores.keySet().size()];
    int j = 0;
    for (String key : wordGroupsAndScores.keySet()) {
        keyLocation[j] = key;
        j++;
    }
    processWordGroupAndScoresRecursive(indices, keyLocation, template);
}

private void processWordGroupAndScoresRecursive(int[] indices, String[] keyLocation, TemplateBean template) {
    processWordGroupAndScoresWithIndices(indices, keyLocation, template);
    boolean changedIndices = false;
    for (int index = indices.length - 1; index >= 0; index--) {
        if (indices[index] < wordGroupsAndScores.get(keyLocation[index]).size() - 1) {
            indices[index]++;
            changedIndices = true;
            break;
        }
    }
    if (changedIndices) {
        processWordGroupAndScoresRecursive(indices, keyLocation, template);
    }
}

private void processWordGroupAndScoresWithIndices(int[] indices, String[] keyLocation, TemplateBean template) {
    System.out.println();
    System.out.println("--Generated combination--");
    UnfinishedInvoice unfinishedInvoice = new UnfinishedInvoice();
    for (int index = 0; index < indices.length; index++) {
        String key = keyLocation[index];
        WordGroupAndScore wordGroupAndScore = wordGroupsAndScores.get(key).get(indices[index]);
        System.out.println("Attribute = " + key);
        System.out.println("WordGroupAndScore = " + wordGroupAndScore);
        System.out.println(";");
        setUnfinishedInvoiceAttribute(key, unfinishedInvoice, Utils.joinWordGroup(wordGroupAndScore.wordGroup, " "), wordGroupAndScore.score);
    }
    System.out.println();
    unfinishedInvoice.verify();
    if (templateMap.containsKey(template)) {
        templateMap.get(template).add(unfinishedInvoice);
    }
    else {
        List<UnfinishedInvoice> list = new ArrayList<>();
        list.add(unfinishedInvoice);
        templateMap.put(template, list);
    }
}

Let's take a more clear look at what it produces, let us only work with the indices, and not with real data anymore.

Let's say this is the input: [1, 1, 2, 1, 0]. With it being the characterization of a map as a list, with as elements the index of the element in the lists inside the original map. We start by the combination where the last elements from the map is being taken.

With my failing code we get as output:

• [1, 1, 2, 1, 0]
• [1, 1, 2, 0, 0]
• [1, 1, 1, 0, 0]
• [1, 1, 0, 0, 0]
• [1, 0, 0, 0, 0]
• [0, 0, 0, 0, 0]

This is not correct as there are a lot of values missing, for example [0, 0, 0, 1, 0] is missing.

What is going wrong here?

Answer 1

Sample pseudo-code using a recursive function. Each level of recursion processes one list by taking all the elements one by one, putting them in the output variable and recursively calling itself to process the next iteration level.

void allCombinations(Map<A, List<B>> input, Map<A, B> output){
   if (input not empty){
      (x, Y) = input.removeOneElement(); //removes one list from the input
      for each b in Y{
        output.insert(x, b);             //adds the element to the output
        allCombinations(input, output);  //recursively calls itself
        output.remove(x, b);             //removes the element from the output
      }
   }else{
      print(output)                      //here i print the output
   }
}

So this effectively creates sizeof(input) nested loops by using recursion.

You call it using:

allCombinations(input, new Map<A, B>());

Note: if instead of printing the output you want it returned. then change the signature of the method:

void allCombinations(Map<A, List<B>> input, Map<A, B> output, List<Map<A,B>> result)
...
result.add(output); //instead of print(output);

and call it using:

List<Map<A,B>> result = new List<Map<A,B>>();
allCombinations(input, new Map<A, B>(), result);

Answer 2

The below Clojure code solves what you are asking for in a robust, fast, and functional way:

(defn combinations* [acc pairs]
  (if-let [[my-key my-vals] (first pairs)]
    (mapcat
      (fn [my-val]
        (combinations*
          (for [m acc] (assoc m my-key my-val))
          (rest pairs)))
      my-vals)
    acc))

(defn combinations [map]
  (combinations* [{}] (vec map)))

The above code is a recursive solution. What it does in plain English is the following. combinations* is a function, which given a list of possible base maps, and a list of key-to-multiple-values pairs, returns all the possible combinations of associating key-values to the input base maps. This is done in a recursive way. If the list of key-to-multiple-values pairs is empty, then we will not associate anything to the base maps, instead return them unmodified. Else, if there are any pairs, then we take the first key-to-multiple-value pair, and for all the values in it, and for all the base maps given as input, we create all combinations how those key-values can be added to the base maps. This list of combinations of modified base maps will be used as the new base map list for recursively calling combinations*, with the remaining key-to-multiple-values pairs as second parameter. We do this recursion of combining and modifying the base maps until we run out of key-to-multiple-values pairs. At that point, as stated above, we return the unmodified base maps as solutions, and concatenate them together with the solutions from the other branches of the recursion. To initialize the function for solving our problem we have to use a singleton list of an empty map as base maps, which is done in the combinations function. Its only parameter is a multi-map, which it splits into a vector of key-to-multiple-values pairs to call combinations* with it.

This is how to call it:

(combinations {"invoiceNumber" ["0001" "0002"]
               "invoiceDate" ["2013-10-07"]
               "priceExclVAT" [10.00M]
               "highVAT" [2.10M]
               "priceInclVAT" [12.10M 14.10M]})

This is the output:

({"invoiceDate" "2013-10-07",
  "invoiceNumber" "0001",
  "highVAT" 2.10M,
  "priceExclVAT" 10.00M,
  "priceVAT" 12.10M}
 {"invoiceDate" "2013-10-07",
  "invoiceNumber" "0002",
  "highVAT" 2.10M,
  "priceExclVAT" 10.00M,
  "priceVAT" 12.10M}
 {"invoiceDate" "2013-10-07",
  "invoiceNumber" "0001",
  "highVAT" 2.10M,
  "priceExclVAT" 10.00M,
  "priceVAT" 14.10M}
 {"invoiceDate" "2013-10-07",
  "invoiceNumber" "0002",
  "highVAT" 2.10M,
  "priceExclVAT" 10.00M,
  "priceVAT" 14.10M})

Try translating it to Java, or just include Clojure dependencies, add Java class generation directives, and call it directly from Java code, like how explained here. You can also test the above code here, without bothering to set up a Clojure environment locally.

UPDATE

For the sake of discussion and grasping the ideas I am going to add a Java-ified version soon.

UPDATE 2

There you go.

private static List<HashMap<String, Object>> associateInAll(
        List<HashMap<String, Object>> orig, String key, Object val) {

    LinkedList<HashMap<String, Object>> result =
            new LinkedList<HashMap<String, Object>>();

    for (HashMap<String, Object> m : orig) {
        HashMap<String, Object> mCopy = new HashMap<String, Object>(m);
        mCopy.put(key, val);
        result.add(mCopy);
    }

    return result;
}

private static List<HashMap<String, Object>> combinations2(
        List<HashMap<String, Object>> acc,
        List<Entry<String, List<Object>>> pairs) {

    if (!pairs.isEmpty()) {

        Entry<String, List<Object>> first = pairs.get(0);
        String myKey = first.getKey();
        List<Object> myVals = first.getValue();

        LinkedList<Entry<String, List<Object>>> rest =
                new LinkedList<Entry<String, List<Object>>>(pairs);

        rest.removeFirst();

        LinkedList<HashMap<String, Object>> results =
                new LinkedList<HashMap<String, Object>>();

        for (Object myVal : myVals) {

            List<HashMap<String, Object>> newBaseMaps =
                    associateInAll(acc, myKey, myVal);

            List<HashMap<String, Object>> subcombinations =
                    combinations2(newBaseMaps, rest);

            results.addAll(subcombinations);
        }

        return results;
    }

    return acc;
}

private static List<HashMap<String, Object>> combinations(
        HashMap<String, List<Object>> map) {

    LinkedList<HashMap<String, Object>> baseMaps =
            new LinkedList<HashMap<String, Object>>();

    baseMaps.add(new HashMap<String, Object>());

    LinkedList<Entry<String, List<Object>>> pairs =
            new LinkedList<Entry<String, List<Object>>>(map.entrySet());

    return combinations2(baseMaps, pairs);
}

public static void main(String... args) {

    HashMap<String, List<Object>> input =
            new HashMap<String, List<Object>>();

    input.put("invoiceNumber",
            Arrays.<Object>asList("0001", "0002", "0003"));
    input.put("invoiceDate",
            Arrays.<Object>asList("2013-10-07"));
    input.put("priceExclVAT",
            Arrays.<Object> asList(new BigDecimal("10.00")));
    input.put("highVAT",
            Arrays.<Object>asList(new BigDecimal("2.10")));
    input.put("priceInclVAT",
            Arrays.<Object>asList(new BigDecimal("12.10"), new BigDecimal("14.10")));

    List<HashMap<String, Object>> results = combinations(input);

    for (HashMap<String, Object> combination : results) {
        System.out.println("=============================");
        for (Entry<String, Object> entry : combination.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

There is a saying that "you can't always get what you want". Now you got it, but I'm telling you it's not what you need. This code is nothing compared to the Clojure version. It's elegance, performance, reusability is severely crippled. No laziness or streamability, no optimizations with persistent data structures, composability, etc... and it is so long and verbose! By the time I finished writing it I forgot what was in the beginning.

HTH.

Answer 3

Let's assume they all have a size of 3 (for the purpose of the explanation).

Then the indices of what we need to print for the second element will look like:

00000
10000
20000
01000
11000
21000
02000
...

By now I hope you realize that we're actually just counting (in base 3 to be exact).

So, rather than base 3, we just need to increment each element up to its own limit.

To keep my code simple, I just used a String[][] rather than a Map<A, List<B>> (the first element of each row corresponds to A - I used the same data as you did, so it should be easy to decipher).

// some hard-coded data
static String[][] strArr = {{"invoiceNumber", "0001", "0002"},
                            {"invoiceDate", "2013-10-07"},
                            {"priceExclVAT", "10.00"},
                            {"highVAT", "2.10"},
                            {"priceInclVAT", "12.10", "14.10"}};
static int[] indices = new int[strArr.length];

static boolean increment(int index)
{
   // when we can simply increase the current element
   if (indices[index] < strArr[index].length-2)
   {
      indices[index]++;
      return true;
   }
   // when we need to reset this element to 0 and increase the next element
   else
   {
      if (index == strArr.length-1)
         // we reached the end of the last list, so we're done
         return false;
      indices[index] = 0;
      return increment(index+1);
   }
}

static void print()
{
   System.out.println(Arrays.toString(indices));
   for (int i = 0; i < strArr.length; i++)
      System.out.println(strArr[i][0] + ", " + strArr[i][indices[i]+1]);
   System.out.println();
}

public static void main(String[] args)
{
   // simply repeatedly print the output, then increment
   do
   {
      print();
   }
   while (increment(0));
}

Answer 4

Okay, here is my own try: I still do need to test it though, and will not be able to do so, until a later date:

Map<WordGroup, List<ValueAndScore>> wordGroupsAndScores; <- gets intialized somewhere earlier

//Assumes that wordGroupsAndScores does not get changed during the process
private void processWordGroupAndScores() {
    //create all possible templatetoinvoices from wordgroupandscores
    int[] indices = new int[wordGroupsAndScores.keySet().size()];
    for (int index = 0; index < indices.length; index++) {
        indices[index] = 0;
    }
    String[] keyLocation = new String[wordGroupsAndScores.keySet().size()];
    int j = 0;
    for (String key : wordGroupsAndScores.keySet()) {
        keyLocation[j] = key;
        j++;
    }
    processWordGroupAndScoresRecursive(indices, keyLocation);
}

private void processWordGroupAndScoresRecursive(int[] indices, String[] keyLocation) {
    processWordGroupAndScoresWithIndices(indices, keyLocation);
    boolean changedIndices = false;
    for (int index = indices.length - 1; index >= 0; index--) {
        if (indices[index] < wordGroupsAndScores.get(keyLocation[index]).size() - 1) {
            indices[index]++;
            //reset indices to the right
            for (int resetIndex = index + 1; resetIndex < indices.length; resetIndex++) {
                indices[resetIndex] = 0;
            }
            changedIndices = true;
            break;
        }
    }
    if (changedIndices) {
        processWordGroupAndScoresRecursive(indices, keyLocation);
    }
}

private void processWordGroupAndScoresWithIndices(int[] indices, String[] keyLocation) {
    for (int index = 0; index < indices.length; index++) {
        String key = keyLocation[index];
        WordGroupAndScore wordGroupAndScore = wordGroupsAndScores.get(key).get(indices[index]);
        //more processing
    }
    //more processing
}

This gives all possible combinations of the indices from the map, and processes them one by one.

EDIT: Updated the processing function to show how to retrieve elements.

EDIT 2: This answer is wrong. Does generate some combinations, but definitely not all.

EDIT 3: The answer is correct now, tested and working.