Generating all binary numbers based on the pattern

Question

Given a pattern , we need to generate all possible binary numbers by filling the missing places in the pattern by 0 and 1.

E.g. Pattern = "x1x";
Output =  [010, 110, 011, 111]

I solved it by creating a method calculate.

public static List<String> calculate(String input, int currentIndex) {
    List<String> result = new ArrayList<String>();
    if(currentIndex > input.length()-1) {
        result.add("");
        return result;
    }
    for(String fragment: calculate(input, currentIndex + 1)) {
        if(input.charAt(currentIndex)=='x') {
            result.add('0' + fragment);
            result.add('1' + fragment);
        }
        else {
            result.add(input.charAt(currentIndex) + fragment);
        }
    }
    return result;
}

Is there some way in which we can leverage the given pattern and design a much Faster and/or cleaner solution. I already know that non-recursive solution will be better. Java 8 features are also welcome.

Answer 1

public class Main {

    static final class BinaryStringList extends AbstractList<String> {

        private final char[] chars;
        private final int size;
        private final StringBuilder sb = new StringBuilder();

        BinaryStringList(String pattern) {
            chars = pattern.toCharArray();
            int count = 0;
            for (char c : chars) {
                if (c != '0' && c != '1' && c != 'x') {
                    throw new IllegalArgumentException();
                }
                if (c == 'x') {
                    count++;
                    if (count > 30) {
                        throw new IllegalArgumentException();
                    }
                }
            }
            size = (int) Math.pow(2, count);
        }

        @Override
        public int size() {
            return size;
        }

        @Override
        public String get(int i) {
            if (i < 0 || i >= size) { throw new IndexOutOfBoundsException(); }
            sb.setLength(0);
            int place = 0;
            for (char a : chars) {
                sb.append(a == 'x' ? ((i >> place++ & 1) == 0 ? '0' : '1') : a);
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        System.out.println(new BinaryStringList("0xx1x"));
    }
}

The advantage of this approach is that instantiating a new BinaryStringList is virtually instantaneous. It's only when you iterate over it that it actually does any work.

Answer 2

While recursion is undoubtedly more elegant, it is also easy to write a function which takes a pattern and a binary string, and produces the next binary string according to the pattern. Then you just need to start with the string created by changing all the x's in the pattern to 0s, and iterate through successors until you reach a string which doesn't have one.

To find the successor for a string given a pattern, iterate backwards through both the string and the pattern. At each character position:

• If the pattern character is x:
  • if the string character is 1, change it to 0.
  • if the string character is 0, change it to 1 and return True.
• Otherwise, the pattern character should match the string character. In any event, continue with the loop.

If the loop does not terminate with a return, then there is no successor and the function should return False. At this point, the string is reinitialized to the initial value.

---

Iterating backwards through the pattern/string produces the values in lexicographic order. If you don't care about the order in which the values are produced, the code might be slightly simpler if you iterate forwards.

In Java, strings are immutable so you can't just mutate the input string. If you need to create a copy of the string, you can't just return where the above algorithm indicates a return; you need to complete the copy. If you use a StringBuilder, it will definitely be easier to work in the opposite direction.

Answer 3

If there are n occurrences of the character x, you can enumerate the possible bit combinations for the x positions by incrementing a counter from 0 to 2^n - 1. Then take one of the bits from the counter to decide for each x if it should be substituted by 0 or 1.

So the outline of the algorithm is:

1. Count number of occurrences of x.
2. Loop from 0 to 2^n - 1.
   1. Substitute each x with a bit from the counter.
   2. Output result.

This is limited to 63 occurrences of x, since we run out of room in a long otherwise. But it would take a very, very long time to enumerate more than 2^63 solutions anyway, so I don't think this is a practical concern.

Code:

private static void enumBitPatterns(String pattern) {
    int len = pattern.length();

    int xCount = 0;
    for (int iChar = 0; iChar < len; ++iChar) {
        if (pattern.charAt(iChar) == 'x') {                
            ++xCount;
        }
    }

    StringBuilder builder = new StringBuilder(len);

    long enumCount = 1L << xCount;
    for (long iEnum = 0; iEnum < enumCount; ++iEnum) {
        builder.delete(0, len);
        long val = iEnum;

        for (int iChar = 0; iChar < len; ++iChar) {
            char ch = pattern.charAt(iChar);                
            if (ch == 'x') {
                builder.append((char)('0' + (val & 1)));
                val >>= 1;
            } else {
                builder.append(ch);
            }
        }

        System.out.println(builder);
    }
}

Answer 4

On reflection, using recursion and a call back is much more efficient way of doing this. Note: this creates very few objects (possibly 3 regardless of the number of results).

public static void main(String[] args) {
    printForPattern("x1x", System.out::println);
}

private static void printForPattern(String pattern, Consumer<CharSequence> consumer) {
    printForPattern(pattern, new StringBuilder(), consumer);
}

private static void printForPattern(String pattern, StringBuilder sb, Consumer<CharSequence> consumer) {
    int length = sb.length();
    if (pattern.length() == length) {
        consumer.accept(sb);
        return;
    }
    char ch = pattern.charAt(length);
    if (ch == 'x' || ch == '0') {
        sb.append('0');
        printForPattern(pattern, sb, consumer);
        sb.setLength(length);
    }
    if (ch == 'x' || ch == '1') {
        sb.append('1');
        printForPattern(pattern, sb, consumer);
        sb.setLength(length);
    }
}

To add this to a list you can do

List<String> results = ...
printForPattern("x1x", s -> results.add(x.toString()));

---

You can;

• count the number of wildcards or xs. This is the number of bits you need to iterate over.
• iterate over 2^^{number of x's) and this will give you all possible bits for those x.
• merge these generated x with the provided bit pattern.