1

I've a string, which is as follows,

x y z

and a corresponding HashMap as follows,

{
  x: [1,2,5,6,7],
  y: [3,4],
  z: [3,8,9,10]
}

I need to generate all possible combinations of the string x y z. So output will be as follows,

1 3 3
1 3 8
1 3 9
... so on

Note that, number of characters can be different and the keys in the hash will be same as number of variables in the string. Another example could be as follows,

x y

Corresponding HashMap as follows,

{
  x: [3,5],
  y: [4]
}

I've tried coding using 2 for-loops, but looks like that is not the right way to go about. I've tried, something as follows,

List<String> permutations = new List<>();
for(int i = 0; i < Str.length; i++) {
  for (Map.Entry<String, List<Integer>> entry : map.entrySet()) {
    for(Integer val : entry. getValue()){
      //substitute
    }
    permutations.add(<substitured-string>);
  }
}

I couldn't think of writing a code which hash dynamic number of for loops. How do I solve this problem of dynamic for loops to iterate?

Abhishek
  • 6,912
  • 14
  • 59
  • 85
  • Think about how you would do it manually, think about what information you would need to maintain, and how to express that as an array? Then write that code? – Gem Taylor Oct 24 '19 at 11:03
  • I think, I need 4th loop to iterate. But looks like the placement of the loop is not right or I'm missing something. – Abhishek Oct 24 '19 at 11:04
  • The keyword you are looking for is Cartesian product and not permutation. – Eritrean Oct 24 '19 at 11:07
  • I think this answer can help ==> https://stackoverflow.com/a/51470002/2101117 It's in JavaScript but I am sure You can understand it. :) – Aleksandar Oct 24 '19 at 11:10
  • 1
    @Aleksandar thank you.. Yes, I understand javascript :) Let me try it and get back to see if it works or not. – Abhishek Oct 24 '19 at 11:12
  • @Eritrean huh.. Yes, it looks like a cartesian product. Thanks for hint, I think I can move forward. – Abhishek Oct 24 '19 at 11:13
  • Possible duplicate of [Cartesian product of arbitrary sets in Java](https://stackoverflow.com/questions/714108/cartesian-product-of-arbitrary-sets-in-java) – Konrad Höffner Oct 25 '19 at 07:56

1 Answers1

0

You can solve this using recursion. May be something like this 

private static void findCombination(List<String> ListOfCombinations,
                                Map<String, int[]> inputMap,
                                List<String> keys,
                                String combination,
                                int level, int index) {
String str = combination;
if (level < keys.size()) {
   int[] values = inputMap.get(keys.get(level));
    if (index < values.length) {
    str = str + values[index];
    if (level == keys.size() - 1) {
        ListOfCombinations.add(str);
        System.out.println(str);
        if (index == values.length - 1) {
            return;
        } else {
            findCombination(ListOfCombinations, inputMap, keys, combination, level, index + 1);
            return;
        }
    } else {
        if (level < keys.size() - 1) {
            findCombination(ListOfCombinations, inputMap, keys, str, level + 1, 0);
            findCombination(ListOfCombinations, inputMap, keys, combination, level, index + 1);
        }
    }
} else {
    return;
}
if (level < keys.size() - 1) {
    if (combination.isEmpty() && level > 0) {
        findCombination(ListOfCombinations, inputMap, keys, combination, level - 1, ++index);
    }
  }
 }
}

in this level is number of string (x,y,z then level can be from 0-2) at each level will pick one number from respective list and there can be n number of levels

for your input below is the output generated from above code 1 3 3
1 3 8
1 3 9
1 3 10
1 4 3
1 4 8
1 4 9
1 4 10
2 3 3
2 3 8
2 3 9
2 3 10
2 4 3
2 4 8
2 4 9
2 4 10
5 3 3
5 3 8
5 3 9
5 3 10
5 4 3
5 4 8
5 4 9
5 4 10
6 3 3
6 3 8
6 3 9
6 3 10
6 4 3
6 4 8
6 4 9
6 4 10
7 3 3
7 3 8
7 3 9
7 3 10
7 4 3
7 4 8
7 4 9
7 4 10

Ankita Agrawal
  • 113
  • 7