Все возможные образцы струн

Question

Когда у меня есть строка, содержащая несколько «P» или «S», например, «PPP», «PSP», «PSSSPPS», «SPSPSS», и мне нужно найти все шаблоны, где P заменяется на «Q» или «R» и S заменяется на «T» или «U».

например, «P» -> output [«Q», «R»]; вход «PP» -> выход [«QQ», «QR», «RR», «RQ»]; input "PS" => output ["QT", "QU", "RT", "RU"];

Как я могу реализовать эту процедуру? Дело в том, что числа P и S не являются фиксированными.

Я хотел бы использовать Java, однако, пожалуйста, дайте мне пример алгоритма.

String[] getAllPatterns(String toBeChanged){
   List<Integer> pPlace = new ArrayList<>();
   List<Integer> sPlace = new ArrayList<>();
   for (int i = 0; i < toBeChanged.length(); i++) {
        char c = toBeChanged.charAt(i);
        if (c == 'P') pPlace.add(i);
        if (c == 'S') sPlace.add(i);
    }
    int numP = pPlace.size();
    int numS = sPlace.size();
    int numCase = (int) Math.round(Math.pow(2, numP) * Math.pow(2, numS)); // 2 is P-> Q or R; S -> T or U
    String[] allcases = new String[numCase];
       .................
  return allcases;
}



getAllPatterns("PS"); //-> {"QT","QU","RT","RU"}
getAllPatterns("SP"); //-> {"TQ","UQ","TR","UR"}

В этом случае «P» может быть только «Q» или «R», но в будущем возможные символы также будут переменными.

«P» может быть » P1 "," P2 "," P3 ", ... или" Pn "

Answer 1

Поскольку каждый входной символ заменяется одним из 2 символов, выбор замены точно соответствует размеру.

Таким образом, чтобы go проходил через все комбинации N-буквенного ввода, вы можете выполнять итерацию по всем значения N-разрядного числа.

Для построения всех комбинаций в List потребуется много памяти, поэтому использование int для перебора значений и ограничение длины ввода до 30, не должны Это не проблема.

В этом случае заменяющими символами являются фактически следующие два символа ASCII, поэтому мы можем вычислить заменяющий символ как replacementChar = inputChar + 1 + bit.

Это означает, что код может выглядеть примерно так:

static List<String> generatePatterns(String input) {
    if (! input.matches("[PS]{0,30}"))
        throw new IllegalArgumentException("Invalid input: " + input);
    final int end = 1 << input.length();
    char[] chars = new char[input.length()];
    List<String> result = new ArrayList<>(end);
    for (int combo = 0; combo < end; combo++) {
        for (int i = input.length() - 1, bits = combo; i >= 0; i--, bits >>>= 1)
            chars[i] = (char) (input.charAt(i) + 1 + (bits & 1));
        result.add(new String(chars));
    }
    return result;
}

Тесты

for (String input : new String[] {"", "P", "PP", "PS", "PPP", "PSP", "PSSSPPS", "SPSPSS"}) {
    List<String> result = generatePatterns(input);
    System.out.println(input + " -> " + result);
}

Вывод

 -> []
P -> [Q, R]
PP -> [QQ, QR, RQ, RR]
PS -> [QT, QU, RT, RU]
PPP -> [QQQ, QQR, QRQ, QRR, RQQ, RQR, RRQ, RRR]
PSP -> [QTQ, QTR, QUQ, QUR, RTQ, RTR, RUQ, RUR]
PSSSPPS -> [QTTTQQT, QTTTQQU, QTTTQRT, QTTTQRU, QTTTRQT, QTTTRQU, QTTTRRT, QTTTRRU, QTTUQQT, QTTUQQU, QTTUQRT, QTTUQRU, QTTURQT, QTTURQU, QTTURRT, QTTURRU, QTUTQQT, QTUTQQU, QTUTQRT, QTUTQRU, QTUTRQT, QTUTRQU, QTUTRRT, QTUTRRU, QTUUQQT, QTUUQQU, QTUUQRT, QTUUQRU, QTUURQT, QTUURQU, QTUURRT, QTUURRU, QUTTQQT, QUTTQQU, QUTTQRT, QUTTQRU, QUTTRQT, QUTTRQU, QUTTRRT, QUTTRRU, QUTUQQT, QUTUQQU, QUTUQRT, QUTUQRU, QUTURQT, QUTURQU, QUTURRT, QUTURRU, QUUTQQT, QUUTQQU, QUUTQRT, QUUTQRU, QUUTRQT, QUUTRQU, QUUTRRT, QUUTRRU, QUUUQQT, QUUUQQU, QUUUQRT, QUUUQRU, QUUURQT, QUUURQU, QUUURRT, QUUURRU, RTTTQQT, RTTTQQU, RTTTQRT, RTTTQRU, RTTTRQT, RTTTRQU, RTTTRRT, RTTTRRU, RTTUQQT, RTTUQQU, RTTUQRT, RTTUQRU, RTTURQT, RTTURQU, RTTURRT, RTTURRU, RTUTQQT, RTUTQQU, RTUTQRT, RTUTQRU, RTUTRQT, RTUTRQU, RTUTRRT, RTUTRRU, RTUUQQT, RTUUQQU, RTUUQRT, RTUUQRU, RTUURQT, RTUURQU, RTUURRT, RTUURRU, RUTTQQT, RUTTQQU, RUTTQRT, RUTTQRU, RUTTRQT, RUTTRQU, RUTTRRT, RUTTRRU, RUTUQQT, RUTUQQU, RUTUQRT, RUTUQRU, RUTURQT, RUTURQU, RUTURRT, RUTURRU, RUUTQQT, RUUTQQU, RUUTQRT, RUUTQRU, RUUTRQT, RUUTRQU, RUUTRRT, RUUTRRU, RUUUQQT, RUUUQQU, RUUUQRT, RUUUQRU, RUUURQT, RUUURQU, RUUURRT, RUUURRU]
SPSPSS -> [TQTQTT, TQTQTU, TQTQUT, TQTQUU, TQTRTT, TQTRTU, TQTRUT, TQTRUU, TQUQTT, TQUQTU, TQUQUT, TQUQUU, TQURTT, TQURTU, TQURUT, TQURUU, TRTQTT, TRTQTU, TRTQUT, TRTQUU, TRTRTT, TRTRTU, TRTRUT, TRTRUU, TRUQTT, TRUQTU, TRUQUT, TRUQUU, TRURTT, TRURTU, TRURUT, TRURUU, UQTQTT, UQTQTU, UQTQUT, UQTQUU, UQTRTT, UQTRTU, UQTRUT, UQTRUU, UQUQTT, UQUQTU, UQUQUT, UQUQUU, UQURTT, UQURTU, UQURUT, UQURUU, URTQTT, URTQTU, URTQUT, URTQUU, URTRTT, URTRTU, URTRUT, URTRUU, URUQTT, URUQTU, URUQUT, URUQUU, URURTT, URURTU, URURUT, URURUU]