multi-recursive replacement function I wrote a function for creating all possible translations of a source string, based on a multiple translation map. It works, but generates a lot of intermediate maps (see line marked with *). Is there a better solution? Maybe a more general solution to the "all possible combinations" problem?:

/**
 * &lt;p&gt;Add to 'targets' all possible variations of 'source', with replacements defined by 'translationsMap'.
 * &lt;p&gt;For example, after the following call:
 * &lt;p&gt;addAllReplacements("put the X on the Y", {X =&gt; {"cake","egg"}, Y =&gt; {"table","chair"}, targets)
 * &lt;p&gt;targets should contain the following strings:
 * &lt;p&gt;"put the cake on the table", "put the cake on the chair", "put the egg on the table", "put the egg on the chair"
 */
public static void addAllReplacements (String source, Map&lt;String, Set&lt;String&gt;&gt; translationsMap, Set&lt;String&gt; targets) {
    if (translationsMap.isEmpty()) {
        // no more replacements:
        targets.add(source);
    } else {
        // pick an entry from the map:
        Entry&lt;String, Set&lt;String&gt;&gt; e = translationsMap.entrySet().iterator().next();
        String text = e.getKey();
        Set&lt;String&gt; translations = e.getValue();

        // Create a new translation map, without the currently translated text, for the recursive call:
        HashMap&lt;String, Set&lt;String&gt;&gt; newTranslationMap =  
                         new HashMap&lt;String, Set&lt;String&gt;&gt;(translationsMap);  // *
        newTranslationMap.remove(text);

        for (String translation: translations) {
                    addAllReplacements(
                        source.replace(text, translation),
                        newTranslationMap,
                        targets);
        }
    }
}
You are using the Map more like a list...

EDIT: this is NOT working:

You could create an object to hold one translation ({X => {"cake","egg"}) then instead of all the Maps you could use a List (of those translations) and always remove and use the first element and pass the shorter list to the next call of your method.

EDIT: this IS working:

You could use a List with the translation and add an index parameter in you method to know which element from the list use. Then you increment the index once before making the recursive calls...

Here is some code (without constructors getters etc...):

public class Translations {
    final String key;
    final Set&lt;String&gt; translations;
}


public static void addAllReplacements_2 (String source,List&lt;Translations&gt; translationsList, final int index, Set&lt;String&gt; targets) {
    if (index == (translationsList.size())) {
        // no more replacements:
        targets.add(source);
    } else {
        // pick an entry
        Translations translations = translationsList.get(index);
        String text = translations.getKey();
        Set&lt;String&gt; translationValues = translations.getTranslations();

        final int nextIndex = index+1;

        for (String translationValue: translationValues) {
            addAllReplacements_2(
                    source.replace(text, translationValue),
                    translationsList,nextIndex,
                    targets);
        }

    }
}