find the correct algorithme to find all the possible binary combination

user_13205693 0
Viewed 75

I'm trying to write a non-recursive Java method called showStar, which takes a string, and generates ALL possible combinations of that string without the mask “*” characters.

receiving this as an input "1011*00*10", 
the method `showStar` will display output like:
1011000010
1011000110
1011100010
1011100110

I tried this way, however, as soon as the number of possible cases is more than the String length, the output is not exact.

Here is my code.

public static void showStar(String s){
        String save;
        int count = 0;
        int poss;

        save = s.replace('*','0');
        StringBuilder myString = new StringBuilder(save);

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '*' && myString.charAt(i) == '0') {
                myString.setCharAt(i, '1');
                System.out.println(myString);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '*' && myString.charAt(i) == '1') {
                myString.setCharAt(i, '0');
                System.out.println(myString);
            }
        }

        }
algorithm java
2 Answers

Say there are k *s. Then there are 2^k solutions. You can generate these by copying the bits from the integers 0 - 2^k-1 in order. (adding sufficient leading zeroes)

E.g. 1**1:

0 = 00 => 1001
1 = 01 => 1011
2 = 10 => 1101
3 = 11 => 1111
user_20410770

Here a recursive algoritm works just perfectly:

  1. You check if an input string contains an asterisk '*' by using an x = str.indexOf('*');
  2. If no asterisk is present (x == -1), you just print the string and return
  3. Otherwise, you replace the asterisk at the position to '0' and '1' and call showStar() recursively for both replacements
public static void showStar(String str) {
    int x = str.indexOf('*');
    if(x == -1) {
        System.out.println(str);
        return;
    }
    String prefix = str.substring(0, x);
    String suffix = str.substring(x + 1);
    for (char i = '0'; i <= '1'; i++) {
        showStar(prefix + i + suffix);
    }
}

Update
In non-recursive implementation we need to collect the asterisk positions, then prepare a binary representation and set appropriate bits at the known positions:

public static void showStar(String str) {
    int[] xs = IntStream.range(0, str.length())
                        .filter(i -> str.charAt(i) == '*')
                        .toArray();
    int num = (int) Math.pow(2, xs.length); // 2^n variants for n asterisks
    String format = xs.length > 0 ? "%" + xs.length + "s" : "%s"; // fix if no '*'

    for (int i = 0; i < num; i++) {
        String bin = String.format(format, Integer.toBinaryString(i))
                           .replace(' ', '0');  // pad leading zeros
        StringBuilder sb = new StringBuilder(str);

        // set 0 or 1 in place of asterisk(s)
        for (int j = 0; j < xs.length; j++) {
            sb.setCharAt(xs[j], bin.charAt(j));
        }
            
        System.out.println(sb);
    }
}
user_132798310
Related