So this problem has been taunting me for days. Any help is greatly appreciated! I have made a LinkedHashMap which stores possible combinations for each part of a string and I'm trying to get all the permutations in an ArrayList of Strings, while maintaing the string order. For example if the map is: a=ab, b=c The combinations would be:

ab
ac
abb
abc

I have tried simply looping each keys and values list, heap's algorithm which didn't work out for keeping the order of elements and also tried using recursion but i wasn't sure how. If anyone could point me in the right direction or hint me, that would be great. Thanks

Another map example of what im trying to do.
If the map is: A=a, B=b
Output is:

AB (key1, key2)
Ab (key1, value2)
aB (value1, key2)
ab (value1, value2)

I basically want every combination of the whole map in order while alternating between keys and values of the map.

CodePudding user response：

Try this.

static List<String> possiblePermutations(Map<String, String> map) {
    int size = map.size();
    List<Entry<String, String>> list = new ArrayList<>(map.entrySet());
    List<String> result = new ArrayList<>();
    new Object() {
        void perm(int i, String s) {
            if (i >= size) {
                result.add(s);
                return;
            }
            Entry<String, String> entry = list.get(i);
            perm(i   1, s   entry.getKey());
            perm(i   1, s   entry.getValue());
        }
    }.perm(0, "");
    return result;
}

public static void main(String[] args) {
    Map<String, String> map = new LinkedHashMap<>();
    map.put("a", "ab");
    map.put("b", "c");
    map.put("x", "y");
    List<String> result = possiblePermutations(map);
    System.out.println(result);
}

output:

[abx, aby, acx, acy, abbx, abby, abcx, abcy]

CodePudding user response：

It's very simple ...

1. Let's say the number of entries in your map is N
2. There is a 1-to-1 mapping between each possible permutation of such strings and an array boolean of length N. If the array has a true in position K, we pick the key from map entry K, otherwise we pick the value.
3. Therefore, to generate all possible permutations you need to generate all possible boolean arrays (same as binary numbers) of length N and then use each one to create a corresponding string.