根据模式生成所有二进制数

给定一个模式，我们需要通过填充模式中缺少的位置0和1来生成所有可能的二进制数。

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

我通过创建方法calculate解决了它。

 public static List calculate(String input, int currentIndex) { List result = new ArrayList(); 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; } 

我们是否可以通过某种方式利用给定的模式并设计更快速和/或更清晰的解决方案。 我已经知道非递归解决方案会更好。 Java 8的function也很受欢迎。

Answer 1

经过反思，使用递归和回调是更有效的方法。 注意：这会创建非常少的对象（无论结果数量多少，都可能为3）。

 public static void main(String[] args) { printForPattern("x1x", System.out::println); } private static void printForPattern(String pattern, Consumer consumer) { printForPattern(pattern, new StringBuilder(), consumer); } private static void printForPattern(String pattern, StringBuilder sb, Consumer 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); } } 

要将其添加到列表中，您可以执行此操作

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

---

您可以;

• 计算通配符或x s的数量。 这是您需要迭代的位数。
• 迭代超过2 ^^ {x的数量），这将为这些x提供所有可能的位。
• 将这些生成的x与提供的位模式合并。

Answer 2

如果出现n字符x ，则可以通过将计数器从0递增到2^n - 1来枚举x位置的可能位组合。 然后从计数器中取出一个位来决定每个x是否应该用0或1代替。

所以算法的大纲是：

1. 计算x的出现次数。
2. 循环从0到2^n - 1 。
   1. 用计数器中的一位代替每个x 。
   2. 输出结果。

这仅限于63次出现x ，因为我们会耗尽long 。 但是，无论如何都要花费很长时间来计算超过2 ^ 63个解决方案，所以我认为这不是一个实际问题。

码：

 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

虽然递归无疑更加优雅，但是编写一个带有模式和二进制字符串的函数也很容易，并根据模式生成下一个二进制字符串。 然后你只需要从通过将模式中的所有x更改为0来创建的字符串开始，然后遍历后继，直到找到没有的字符串。

要找到给定模式的字符串的后继者，请向后遍历字符串和模式。 在每个角色位置：

• 如果模式字符是x ：
  • 如果字符串字符为1 ，则将其更改为0 。
  • 如果字符串字符为0 ，则将其更改为1并返回True。
• 否则，模式字符应与字符串字符匹配。 无论如何，继续循环。

如果循环没有以return ，则没有后继，函数应该返回False。 此时，字符串将重新初始化为初始值。

---

向后遍历模式/字符串会以字典顺序生成值。 如果您不关心生成值的顺序，那么如果向前迭代，代码可能会稍微简单一些。

在Java中，字符串是不可变的，因此您不能只改变输入字符串。 如果您需要创建字符串的副本，则不能只返回上述算法指示返回的位置; 你需要完成副本。 如果使用StringBuilder，那么在相反的方向上工作肯定会更容易。

Answer 4

 public class Main { static final class BinaryStringList extends AbstractList { 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")); } } 

这种方法的优点是实例化一个新的BinaryStringList实际上是瞬时的。 只有当你迭代它，它实际上做任何工作。