multi-recursive replacement function

Question

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?:

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

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

        for (String translation: translations) {
                    addAllReplacements(
                        source.replace(text, translation),
                        newTranslationMap,
                        targets);
        }
    }
}

pgras · Accepted Answer · 2013-02-26 10:21:55Z

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<String> translations;
}


public static void addAllReplacements_2 (String source,List<Translations> translationsList, final int index, Set<String> 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<String> translationValues = translations.getTranslations();

        final int nextIndex = index+1;

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

    }
}

This doesn't work. I can remove and use the first element, however, when I will remove the second element in the next recursion level, it won't be available when I get to the second level later. For example, when I try this on the above example, I get: "put the egg on the chair", "put the cake on the chair", "put the X on the table" (the Y translation is first, it is done OK, but the X translation is done only once).
You are right there is a problem with my solution, I edit my post to give a working solution...
This is really a bad example of a recursion. You should not introduce a new index variable, you should pass a reduced list of Translations. And If you have a Translation object, you should do the logic inside the class. In this way, it is nothing else than a data transfer object.

tb- · Answer 2 · 2013-02-27 18:56:03Z

Some thoughts about the given code:

/**
 * <p>Add to 'targets' all possible variations of 'source', with replacements defined by 'translationsMap'.
 * <p>For example, after the following call:
 * <p>addAllReplacements("put the X on the Y", {X => {"cake","egg"}, Y => {"table","chair"}, targets)
 * <p>targets should contain the following strings:
 * <p>"put the cake on the table", "put the cake on the chair", "put the egg on the table", "put the egg on the chair"
 */

It is a good way to provide JavaDoc and it is a very good idea to provide an example. I would just suggest to not use this <p>, instead a <br> or <br /> at the end. Or if you do not like this, you could put everything inside a <pre></pre>.

public static void addAllReplacements (String source, Map<String, Set<String>> translationsMap, Set<String> targets) {

I would avoid this C-Pointer style argument handling in the Java world. Just return the set. As a general rule, you should not modify any method arguments.

public static void addAllReplacements (String source, Map<String, Set<String>> translationsMap, Set<String> targets) {
...
}

This recursion looks a bit confusing and not suitable. I would use an iterative approach:

/**
 * Add to 'targets' all possible variations of 'source', with replacements defined by 'translationsMap'.<br>
 * Example:<br>
 * source = "put the X on the Y"<br>
 * mapStringToReplacementValueSet = {X => {"cake","egg"}, Y => {"table","chair"})<br>
 * <br>
 * => result = ("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 Set<String> getAllReplacementsForSourceAndReplacementMap(final String source, final Map<String, Set<String>> mapStringToReplacementValueSet) {
    // plan: create a result set which contains the source
    // for every entry in the map (which corresponds to one replacement key)
    //   for each replacement values go over all elements in the current set, do the replacement, add it to a new set
    //   make the new set the current set.

    Set<String> result = new HashSet<>(Arrays.asList(source));

    for (final Entry<String, Set<String>> entry : mapStringToReplacementValueSet.entrySet()) {
        final String currentKey = entry.getKey();
        if (!source.contains(currentKey))
            continue;
        final Set<String> newResult = new HashSet<>();
        final Set<String> currentValue = entry.getValue();
        for (final String setItem : currentValue) {
            for (final String resultArrayItem : result)
                newResult.add(resultArrayItem.replace(currentKey, setItem));
        }
        result = newResult;
    }

    return result;
}

Edit: If you use this Translations class, you could simplify the loop to:

    for (Translation translationsItem : translations)
        result = translationsItem.apply(result)

And the logic goes inside the Translation class.

asked	2 months ago
viewed	75 times
active	2 months ago

multi-recursive replacement function

2 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged java recursion combinatorics or ask your own question.

Community Bulletin

multi-recursive replacement function

2 Answers

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java recursion combinatorics or ask your own question.

Community Bulletin

Related