Multiple string replacement in a single string generating all possible combinations

Viewed 78

I'm trying to replace multiple words in a string with multiple other words. The string is

I have sample {url} with time to {live}

Here the possible values for {url} are

  • point1
  • point2

Possible values for {live} are

  • 10
  • 20

The four possible answers are

  1. I have sample point1 with time to 10
  2. I have sample point1 with time to 20
  3. I have sample point2 with time to 10
  4. I have sample point2 with time to 20

This can also increase to three.

I have {sample} {url} with time to {live}

What would be best data structures and good approach to solve this problem ?

3 Answers

You can do it something like:

public static void main(String[] args) {
    String inputStr = "I have {sample} {url} with time to {live}";
    Map<String, List<String>> replacers = new HashMap<String, List<String>>(){{
        put("{sample}", Arrays.asList("point1", "point2"));
        put("{live}", Arrays.asList("10", "20"));
        put("{url}", Arrays.asList("url1", "url2", "url3"));
    }};
    for (String variant : stringGenerator(inputStr, replacers)) {
        System.out.println(variant);
    }
}

public static List<String> stringGenerator(String template, Map<String, List<String>> replacers) {
    List<String> out = Arrays.asList(template);

    for (Map.Entry<String, List<String>> replacerEntry : replacers.entrySet()) {
        List<String> tempOut = new ArrayList<>(out.size()*replacerEntry.getValue().size());
        for (String replacerValue : replacerEntry.getValue()) {
            for (String variant : out) {
                tempOut.add(variant.replace(replacerEntry.getKey(), replacerValue));
            }
        }

        out = tempOut;
    }
    return out;
}

also you can try make similar solution with recursion

You can use a template string and print the combinations using System.out.format method like below:

public class Combinations {
    public static void main(String[] args) {
        String template = "I have sample %s with time to %d%n"; //<-- 2 arguments case
        String[] points = {"point1", "point2"};
        int[] lives = {10, 20};
        for (String point : points) {
            for (int live : lives) {
                System.out.format(template, point, live);
            }
        }
    }
}

The code solves the 2 argument case but it can be easily extended to the 3 cases substituting the sample word with another %s in the template and a triple loop. I'm using the simplest array structures, it is up to you decide which structure is the more adapt for your code.

Unless you want the hardcoded solution with simple nested loops shown in Dariosicily's answer, you will need to store "replacee-replacements" pairings, for example the string {url} paired with a list of strings point1 and point2. A simple class can do that, like

class StringListPair{
    public final String s;
    public final List<String> l;
    public StringListPair(String s,List<String> l){
        this.s=s;
        this.l=l;
    }
}

and then a list of replacements can be initialized as

List<StringListPair> mappings=Arrays.asList(
        new StringListPair("{url}",Arrays.asList("point1","point2")),
        new StringListPair("{live}",Arrays.asList("10","20","30")));

(If someone wants to totally avoid having a helper class, these are all strings, so a List<List<String>> can do the job too, having "{url}","point1","point2" lists inside, just then we would have to fight with indexing the inner lists everywhere)

Then two common approaches pop into my mind: a recursive one, generating all possible combinations in a single run, and a direct-indexing one, numbering all combinations and generating any of them directly upon request. Recursion is simpler to come up with, and it has no significant drawbacks if all the combinations are needed anyway. The direct approach generates a single combination at a time, so if many combinations are not going to be used, it can spare a lot of memory and runtime (for example if someone would need a single randomly selected combination only, out of millions perhaps).

Recursion will be, well, recursive, having a completed combination generated in its deepest level, thus it needs the following:

  • the list of combinations (because it will be extended deep inside the call-chain)
  • the mappings
  • the candidate it is working on at the moment
  • something to track what label it is supposed to replace a the moment.

Then two things remain: recursion has to stop (when no further labels remain for replacement in the current candidate, it is added to the list), or it has to replace the current label with something, and proceed to the next level.
In code it can look like this:

static void recursive(List<String> result,List<StringListPair> mappings,String sofar,int partindex) {
    if(partindex>=mappings.size()) {
        result.add(sofar);
        return;
    }
    StringListPair p=mappings.get(partindex);
    for(String item:p.l)
        recursive(result,mappings,sofar.replace(p.s,item),partindex+1);
}

level is tracked by a simple number, partindex, current candidate is called sofar (from "so far"). When the index is not referring to an existing element in mappings, the candidate is complete. Otherwise it loops through the "current" mapping, and calling itself with every replacement, well, recursively.
Wrapper function to creata and return an actual list:

static List<String> userecursive(List<StringListPair> mappings,String base){
    List<String> result=new ArrayList<>();
    recursive(result, mappings, base, 0);
    return result;
}


The direct-indexing variant uses some maths. We have 2*3 combinations in the example, numbered from 0...5. If we say that these numbers are built from i=0..1 and j=0..2, the expression for that could be index=i+j*2. This can be reversed using modulo and division operations, like for the last index index=5: i=5%2=1, j=5//2=2. Where % is the modulo operator, and // is integer division. The method works higher "dimensions" too, just then it would apply modulo at every step, and update index itself with the division as the actual code does:

static String direct(List<StringListPair> mappings,String base,int index) {
    for(StringListPair p:mappings) {
        base=base.replace(p.s,p.l.get(index % p.l.size())); // modulo "trick" for current label
        index /= p.l.size();                    // integer division throws away processed label
    }
    return base;
}

Wrapper function (it has a loop to calculate "2*3" at the beginning, and collects combinations in a list):

static List<String> usedirect(List<StringListPair> mappings,String base){
    int total=1;
    for(StringListPair p:mappings)
        total*=p.l.size();
    List<String> result=new ArrayList<>();
    for(int i=0;i<total;i++)
        result.add(direct(mappings,base,i));
    return result;
}

Complete code and demo is on Ideone

Related