时间戳

首页 > 解决方案 > 通过递归遍历布尔数组的所有可能性

java - 通过递归遍历布尔数组的所有可能性

问题描述

如果我们有一个由 4 个布尔值组成的数组，那么生成所有可能值的最佳方法是什么？

我想找到一个解决方案，以正确的顺序生成从 0“False”到 4“False”的所有可能性（首先是 0“False”的所有可能性，然后是 1“False”的所有可能性，然后是所有2“假”等的可能性......）：

我试图用递归来做，但我错过了一些东西。

标签： javaalgorithmrecursion

解决方案

好吧，想象一个方法：

void addPossible(ArrayList<String> array, String prefix, int numberOfSlots, int numberFalse) {
}

想象一下这个方法被称为 addPossible(array, "TTT", 1, 0)。在这种情况下，您知道您可以有 1 个正确和没有错误的选择，因此您只需将一个值添加到数组中，即前缀 +“T”，或者在这种情况下为“TTTT”并返回。

现在，多次调用此方法：

for (int index = 0; index < 4; ++index) {
    addPossible(array, "", 4, index);
}

换句话说，我们将使用 4 个插槽来调用它，一次为 0 false，然后为 1 false，以此类推。

在方法内部，您将再次调用该方法，两次。我不会向您展示所有代码，但调用将是：

addPossible(array, prefix + "T", numberOfSlots-1, numberFalse);
addPossible(array, prefix + "F", numberOfSlots-1, numberFalse-1);

第一种情况，因为我们添加了一个 T，所以我们仍然需要所有的 false。第二种情况，因为我们要加一个 F，所以我们需要少一个 false。无论哪种情况，我们都已添加到字符串中，因此剩余的插槽数较少。

还有更多代码要写。您实际上并没有将任何东西推到向量上，也没有完成逻辑。

但也许你会看到这是怎么回事。

推荐阅读