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

Question

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

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

我通过创建方法 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;
}

有没有什么方法可以让我们利用给定的模式并设计出更快和/或更清洁的解决方案。我已经知道非递归解决方案会更好。也欢迎 Java 8 功能。

Answer 1

经过深思熟虑，使用递归和回调是更有效的方法。注意:这会创建非常少的对象(无论结果数量如何，都可能是 3 个)。

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);
    }
}

要将此添加到您可以做的列表中

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

---

你可以；

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