Recursively or iteratively retrieve key-value combinations from a HashMap

Question

I want to retrieve k,v-pairs from a HashMap. The entrys are like this:

a = 3,4
b = 5,6

and so on. I need combinations of these values.

a=3, b=5
a=3, b=6
a=4, b=5
a=4, b=6

I don't know how many keys and how many entrys the values have. With entrySet I can get the values but not combinations. It looks like recursion but how?

Here's my code:

HashMap<String, String[]> map = new HashMap<String, String[]>();

BufferedReader file = new BufferedReader(new FileReader("test.txt"));
String str;

while ((str = file.readLine()) != null) {
    
    // ... logic
    
    map.put(key, value);
}

System.out.println("number of keys: " + map.size());
for (Map.Entry<String, String[]> entry : map.entrySet()) {
    for (String value : entry.getValue()) {
        System.out.println(entry.getKey() + ": " + value);
    }
}
file.close();

I'm not clear: is "a" your key and "3" (from a's list) your value, or is "3" your key from a and "5" your value from b? — Michael Brewer-Davis, Mar 16 '11 at 09:10
a is the key, 3 and 4 are strings. therefore "String[]". the value is String[] — zyamat, Mar 16 '11 at 09:18

score 5 · Answer 1 · answered Mar 16 '11 at 10:25

You can try the following code:

public void mapPermute(Map<String, String[]> map, String currentPermutation) {
    String key = map.keySet().iterator().next(); // get the topmost key

    // base case
    if (map.size() == 1) {          
        for (String value : map.get(key)) {
            System.out.println(currentPermutation + key + "=" + value);
        }
    } else {
        // recursive case
        Map<String, String[]> subMap = new HashMap<String, String[]>(map);

        for (String value : subMap.remove(key)) {
            mapPermute(subMap, currentPermutation + key + "=" + value + ", ");
        }
    }
}

No guarantees on memory efficiency or speed. If you want to preserve the order of the keys in the map, you will have to pass in a TreeMap and change the code to use a TreeMap under the recursive case.

As the base case suggests, I'm assuming you have at least one entry in your map.

score 0 · Answer 2 · edited Aug 13 '21 at 13:34

It looks to me like you really want a MultiMap. In particular, ArrayListMultimap allows duplicate entries:

ArrayListMultimap<String, String> map = ArrayListMultimap.create();

for each line in file:
    parse key k
    for each value in line:
        parse value v
        map.put(k, v);

for (Map.Entry<String, String> entry : map.entries()) {
    String key = entry.getKey();
    String value = entry.getValue();
}

If you want a cartesian product of maps, you could compute that directly using recursion, or you could iterate over the maps: create a list of iterators and iterate odometer-style; when iterator N reaches its end, advance iterator N+1 and reset iterators 1..N.

Just poked around and found this SO question.

So I'd recommend you use guava's Sets.cartesianProduct for the cartesian product. Here's my poking around code, which you could adapt to your input logic:

String key1 = "a";
Set<Integer> values1 = Sets.newLinkedHashSet(Arrays.asList(1, 2, 3, 4));
String key2 = "b";
Set<Integer> values2 = Sets.newLinkedHashSet(Arrays.asList(5, 6, 7));
String key3 = "c";
Set<Integer> values3 = Sets.newLinkedHashSet(Arrays.asList(8, 9));

List<String> keys = Arrays.asList(key1, key2, key3);
Set<List<Integer>> product = Sets.cartesianProduct(values1, values2, values3);
for (List<Integer> values : product) {
    for (int i = 0; i < keys.size(); ++i) {
        String key = keys.get(i);
        int value = values.get(i);
        System.out.print(key + "=" + value + "; ");
    }
    System.out.println();
}

A `HashMultimap` would prevent duplicate entries. But I'm still really unclear on your goal. — Michael Brewer-Davis, Mar 16 '11 at 09:22
ok. i get a text-input. this gets into the map. key is a. the values are stored in a String[]. i need the values later as separate strings. so that is why it is String[] and not just string. i need every combination from the key-value-pairs as in my first post. — zyamat, Mar 16 '11 at 09:25
In that case you just need to check if the key-value pair already exists in the map. — HamoriZ, Mar 16 '11 at 09:27
I think I just got that you want the product of the maps--as in http://stackoverflow.com/questions/714108/cartesian-product-of-arbitrary-sets-in-java — Michael Brewer-Davis, Mar 16 '11 at 09:30
well, it is more like this: http://stackoverflow.com/questions/710670/c-permutation-of-an-array-of-arraylists the method given in your link... how can this be applied to my case? sorry, i am not a really good programmer... — zyamat, Mar 16 '11 at 09:39

score 0 · Answer 3 · answered Aug 13 '21 at 13:16

You can obtain a Cartesian product of map key-value combinations using a map and reduce approach.

Try it online!

Map<String, String[]> map = Map.of(
        "a", new String[]{"3", "4"},
        "b", new String[]{"5", "6"});

List<Map<String, String>> comb = map.entrySet().stream()
        // Stream<List<Map<String,String>>>
        .map(e -> Arrays.stream(e.getValue())
                .map(v -> Map.of(e.getKey(), v))
                .collect(Collectors.toList()))
        // summation of pairs of list into a single list
        .reduce((list1, list2) -> list1.stream()
                // combinations of inner maps
                .flatMap(map1 -> list2.stream()
                        // concatenate into a single map
                        .map(map2 -> {
                            Map<String, String> m = new HashMap<>();
                            m.putAll(map1);
                            m.putAll(map2);
                            return m;
                        }))
                // list of combinations
                .collect(Collectors.toList()))
        // otherwise, an empty list
        .orElse(Collections.emptyList());

// output, order may vary
comb.forEach(System.out::println);

Output, order may vary:

{a=3, b=5}
{a=3, b=6}
{a=4, b=5}
{a=4, b=6}

^{See also: Cartesian product of map values}

Recursively or iteratively retrieve key-value combinations from a HashMap

3 Answers3

Linked