Замена нескольких строк в одной строке, генерирующая все возможные комбинации

Question

Я пытаюсь заменить несколько слов в строке несколькими другими словами. Строка:

У меня есть образец {url} со временем до {live}

Здесь возможные значения {url}:

• point1
• point2

Возможные значения для {live}:

• 10
• 20

Четыре возможных ответа:

1. У меня есть точка выборки1 со временем до 10
2. У меня есть точка выборки1 со временем до 20
3. У меня есть точка выборки2 со временем до 10
4. У меня есть выборка point2 со временем до 20

Это также может увеличиться до трех.

У меня есть {sample} {url} со временем to {live}

Каковы были бы лучшие структуры данных и хороший подход для решения этой проблемы?

Answer 1

Вы можете использовать строку шаблона и распечатать комбинации, используя метод System.out.format, как показано ниже:

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);
            }
        }
    }
}

Код решает случай с двумя аргументами, но его можно легко распространить на три случая, подставив образец слово с другим% s в шаблоне и тройным l oop. Я использую простейшие структуры массивов, и вы сами решаете, какая структура наиболее приспособлена для вашего кода.

Answer 2

Если вам не нужно жестко запрограммированное решение с простыми вложенными циклами, показанное в ответе Дариосицилии, вам потребуется хранить пары «замены-замены», например строку {url} в паре со списком строк point1 и point2. Простой класс может сделать это, как

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

, и затем список замен может быть инициализирован как

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

(Если кто-то хочет полностью избежать использования вспомогательного класса, это все строки, так что List<List<String>> тоже может выполнить эту работу, имея "{url}","point1","point2" списки внутри, и тогда нам придется бороться с индексацией внутренних списков везде)

Тогда мне в голову приходят два общих подхода: рекурсивная, генерирующая все возможные комбинации за один прогон, и прямая индексация, нумерация всех комбинаций и генерация любой из них непосредственно по запросу. Рекурсию проще придумать, и у нее нет существенных недостатков, если все равно нужны все комбинации. Прямой подход генерирует одну комбинацию за раз, поэтому, если многие комбинации не будут использоваться, он может сэкономить много памяти и времени выполнения (например, если кому-то понадобится только одна случайно выбранная комбинация, возможно, из миллионов) .

Рекурсия будет, ну, в общем, рекурсивной, с завершенной комбинацией, созданной на самом глубоком уровне, поэтому ей необходимо следующее:

• список комбинаций (потому что он будет расширен глубоко внутри цепочки вызовов)
• сопоставления
• кандидата, над которым он работает в данный момент
• что-то, чтобы отследить, какую метку он должен заменить на данный момент.

Тогда остаются две вещи: рекурсия должна быть остановлена ​​(когда больше не осталось меток для замены в текущем кандидате, она добавляется в список), или она должна заменить текущую метку чем-то, и переходите к следующему уровню.
В коде это может выглядеть так:

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);
}

уровень отслеживается простым n Умбер, partindex, текущий кандидат называется sofar (от "до сих пор"). Когда индекс не ссылается на существующий элемент в mappings, кандидат завершен. В противном случае он перебирает «текущее» отображение и вызывает себя при каждой замене, ну, рекурсивно.
Функция обертки для создания и возврата фактического списка:

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

---

Прямая индексация Вариант использует некоторые математические. У нас есть 2 * 3 комбинации в примере, пронумерованные от 0 ... 5. Если мы говорим, что эти числа построены из i=0..1 и j=0..2, выражение для этого может быть index=i+j*2. Это можно изменить с помощью операций по модулю и делению, как для последнего индекса index=5: i=5%2=1, j=5//2=2. Где % - оператор по модулю, а // - целочисленное деление. Этот метод работает и с «большими размерами», только тогда он будет применять модуль по каждому шагу и обновлять сам индекс с делением, как это делает действительный код:

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

Функция обертки (у нее есть все oop чтобы вычислить «2 * 3» в начале и собирать комбинации в список):

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

Полный код и демонстрация включены Ideone

Answer 3

Вы можете сделать что-то вроде:

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

, также вы можете попробовать сделать подобное решение с рекурсией