Generate all binary numbers based on a pattern

Question

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

Eg Pattern = "x1x"; Output = [010, 110, 011, 111] 

I solved this by creating a calculate method.

 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 a way by which we can use this template and develop a much faster and / or cleaner solution. I already know that a non-recursive solution would be better. Java 8 features are also welcome.

Answer 1

When reflecting, using recursion and a callback is much more efficient. 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 the list, you can do

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

---

You can:

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

Answer 2

If there are n occurrences of the character x , you can list the possible bit combinations for the x positions, increasing the counter from 0 to 2^n - 1 . Then take one of the bits from the counter to select for each x if it should be replaced with 0 or 1 .

So, the algorithm diagram:

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

This is limited to 63 occurrences of x , because otherwise we end up with the number long . But in any case, it will take a very long time to list more than 2 ^ 63 solutions, so I do not think this is a practical problem.

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 3

 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 the creation of a new BinaryStringList happens almost instantly. It is only when you iterate over it so that it really does some work.

Answer 4

While recursion is undoubtedly more elegant, it is also easy to write a function that takes a pattern and binary string and creates the next binary string according to the pattern. Then you just need to start with the line created by changing all x in the template to 0 s and repeat using successors until you reach a line that does not have it.

To find a successor for the string specified by the pattern, iterate backward along both the string and the pattern. In 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 must match the string character. In any case, continue the cycle.

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

---

Iterating back over a pattern / line results in values ​​in lexicographical order. If you don’t need the order in which the values ​​are produced, the code may be a little easier if you go ahead.

In Java, strings are immutable, so you cannot just mutate the input string. If you need to create a copy of a string, you cannot just go back to where the above algorithm indicates a return; you need to fill out a copy. If you use StringBuilder, then it will definitely be easier to work backwards.