Algorithm to map one key values to another key's values in the Map

Question

I have some Maps which I would like to calculate the cartesian product of. Can someone please suggest a good algorithm:

Data:

Key1    {100,101,102}

Key2    {200,201}

Key3    {300}

Required Output: (Order does matter)

100,200,300
101,200,300
102,200,300
100,201,300
101,201,300
102,201,300

Map is dynamic so Key and values can vary in size.

Thanks.

By the way, this is a cartesian product. The fact that your data are in map does not matter - it's just a couple of sets and you want to combine each member with each other. — Ondra Žižka, Jul 22 '11 at 13:35
For an example of how to calculate this Cartesian product, see http://stackoverflow.com/questions/714108/cartesian-product-of-arbitrary-sets-in-java — Ben, Jul 22 '11 at 13:50

score 1 · Accepted Answer · answered Jul 22 '11 at 16:25

You will want to switch to using a LinkedHashMap so that order is preserved when you're iterating over keys.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class CartesianPrint {

    public static void main(String[] args) {
        Map<Integer,List<Integer>> groupMap = new LinkedHashMap<Integer,List<Integer>>();

        groupMap.put(1,Arrays.asList(new Integer[]{100,101,102}));
        groupMap.put(2,Arrays.asList(new Integer[]{200,201}));
        groupMap.put(3,Arrays.asList(new Integer[]{300}));

        List<List<Integer>> values = new ArrayList<List<Integer>>(groupMap.values());
        int[] printList = new int[values.size()];
        print(values,printList,values.size()-1);        
    }

    static void print(List<List<Integer>> values, int[] printList, int level){
        for (Integer value: values.get(level)) {
            printList[level] = value;
            if(level == 0){
                 System.out.println(Arrays.toString(printList));
            }else{
                 print(values,printList,level-1);
            }
        }       
    }

}

Funny enough. We had also found the similar solution but I'll mark correct for your efforts :) Thank you. — JSS, Jul 22 '11 at 17:03

score 1 · Answer 2 · answered Jul 22 '11 at 17:19

Same as Ondra Žižka, if you don't need a map, take a List it works the same way. Here is a not so optimized way (I should clone instead of recalculating product in recursion. But the idea is still here and its pretty short. I took special care to keep correct order, that's why I run through List backwards.

    public static List<List<Integer>> getCart(List<List<Integer>> a_list) {
        List<List<Integer>> l_result = new ArrayList<List<Integer>>();
        if (a_list == null || a_list.isEmpty()) {
            l_result.add(new ArrayList<Integer>());
            return l_result;
        }
        for (Integer l_value : a_list.get(a_list.size()-1)) {
            List<List<Integer>> l_resultPortion = getCart(a_list.subList(0, a_list.size() - 1));
            for (List<Integer> l_list : l_resultPortion) {
                l_list.add(l_value);
            }
            l_result.addAll(l_resultPortion);
        }
        return l_result;
    }

Ondra Žižka · Answer 3 · 2011-07-22T13:39:43.347

I suggest to create a store of tuples (triplet in your example).

List<List<Integer>> store = new LinkedList();

Then create a Stack of numbers.

Stack<Integer> stack = new Stack();

Then write a recursive function:

In each recursive function call, push the actually processed value of the array into the stack, and add the current tuple to the store.

private static process( Iterator<String> keys ){
    // Bottom-most key
    if( ! keys.hasNext() ){
        // Construct the tuple from the stack and add it to store.
    }
    else {
       String currentKey = keys.next();
       List<Integer> numbers = map.get( currentKey );
       for( int i : numbers ){
          stack.push( i );
          process ( keys );
          stack.pop();  // Dispose processed number.
       }
    }
}

I hope I figured out the problem right (no guarantee). Sorry for not implementing it whole but that's your homework :)

Algorithm to map one key values to another key's values in the Map

3 Answers3