Создание шаблонов из заданной строки в java

Question

С учетом строки str = ab12. Я пытаюсь создать модели, как показано ниже

xbx2 ax1x abxx xx12

Вот еще один пример, чтобы сделать это немного ясно:
Оригинал Строка 182d3c
Требуемый образец:
18xdxc 182x3x 18xx3c 182dxx 18xxxx Смотрите, что 18 постоянна и другие два варьирующихся
x82dxc 1x2d3x xx2d3c 182dxx xx2dxx Просмотреть сейчас 2d является постоянным, другие меняются

так далее и ...

Обратите внимание, что количество x в любом образце должно быть четным.

Я пробовал использовать регулярное выражение, но безрезультатно. , тогда я думал, что может быть генерация двоичного кода. Алгоритм поможет (кажется, что-то вроде двоичного рисунка с x), но все равно меня там нет. :(

Если вам нужна дополнительная информация, пожалуйста, комментарий, я буду рад поделиться.

Любая помощь будет принята с благодарностью!
Спасибо!

Answer 1

12 символов безопасный предел.

Вы можете использовать битовую маску ... Итерацию через 0 to 2^l - 1, (где l = длина строки) и проверьте битное представление i, если количество установленных бит четное. Если это так, отметьте позицию набора бит как x's и сохранить остальную строку.

Этот алгоритм имеет сложность O(l * 2^l), что прекрасно, как max(l) = 12. Таким образом, количество операций будет иметь порядок 2.4e4, что легко достижимо в скважине менее 1 с.

EDIT: В соответствии с поручением, образец кода в Java

EDIT2: Заменил предыдущий код с новым рабочим кодом :)

import java.io.*; 
import java.util.*; 
import java.lang.*; 

public class xes{ 
    public static String convert(int n, int l){ 
     StringBuilder s = new StringBuilder(); 
     int g = 0; 
     while(n>0){ 
      int c = n%2; 
      if(c==0) 
       s.append("0"); 
      else{ 
       s.append("1"); 
       g++; 
      } 
      n/=2; 
     } 
     while(s.length()<l) 
      s.append("0"); 
     if(g%2 == 0) 
      return ("" + s.reverse()); 
     else 
      return "-1"; 
    } 

    public static ArrayList<String> getAllPatterns(String s){ 
     int l = s.length(); 
     int p = (1<<l) - 1;   //because you don't want all x's, so -1. 1<<l is same as power(2,l) 
     ArrayList<String> arr = new ArrayList<String>(); 
     for(int i=1;i<p;i++){  //i started from i=1 since you don't want all characters visible in any string in arraylist...if you want, stat it with 0 
      String z = convert(i,l); 
      if(z.equals("-1")) 
       continue; 
      StringBuilder g = new StringBuilder(s); 
      for(int j=0; j < z.length(); j++){ 
       if(z.charAt(j)=='1') 
        g.setCharAt(j,'x'); 
      } 
      System.out.println(g); 
      arr.add("" + g); 
     } 
     return arr; 
    } 

    public static void main(String args[]){ 
     ArrayList<String> patterns = getAllPatterns("1823"); 
    } 
} 

Это выход:

18xx 
1x2x 
1xx3 
x82x 
x8x3 
xx23 

Для другого входа , 1823ab, я получаю все 30 возможных (6C2 + 6C4) строк в качестве выходных:

1823xx 
182xax 
182xxb 
18x3ax 
18x3xb 
18xxab 
18xxxx 
1x23ax 
1x23xb 
1x2xab 
1x2xxx 
1xx3ab 
1xx3xx 
1xxxax 
1xxxxb 
x823ax 
x823xb 
x82xab 
x82xxx 
x8x3ab 
x8x3xx 
x8xxax 
x8xxxb 
xx23ab 
xx23xx 
xx2xax 
xx2xxb 
xxx3ax 
xxx3xb 
xxxxab