Possible permutations of string based on LinkedHashMap?

Question

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.

Answer 1

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]