生成所有二进制数的基础上图案 [英] Generating all binary numbers based on the pattern

问题描述

给定的图案，我们需要通过由0和1填充的遗漏地的图案，以产生所有可能的二进制数。

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]

我通过创建一个方法计算解决它。

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功能也都欢迎。

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.

推荐答案

在思考，用递归和回调是更有效的这样做的方法。注：（结果数不管可能3）这造成非常少的物体

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;

• 计算通配符的数量或 X 秒。这就是你需要遍历位数。
• 在迭代2 ^^ {X的数量），这会给你一切可能的位为那些 X 。
• 在合并这些生成的 X 与所提供的位模式。

• 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.

这篇关于生成所有二进制数的基础上图案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！