javascript - 灵活的算法来计算所有可能场景的可能性

Question

我一直在努力寻找或弄清楚算法。

任务:基本上，我有一系列概率:

var input = [0.1, 0.2, 0.3, 0.1];

让我们相应地命名这些输入:A、B、C 和 D。

我还有一个变量“m”，它可以告诉我需要发生多少这样的事情才能得到结果。例如:

var m = 2;

这个变量 m 告诉我如果这两个(或更多)概率中的任何一个发生，事件就会发生。

所以在这种情况下，对于事件的发生，事件发生的所有可能方式是:

ABCD美国广播公司ABDBCDAB空调广告公元前蓝光与光碟

现在我需要计算它们的概率，我已经有了计算 AND 和 OR 的算法(其中输入只是一个概率数组)。

和:

if (input.length > 0) {
    output = 1;
}
for (i = 0; i < input.length; i++) {
    output = input[i] * output;
}

或者:

if (input.length > 0) {
    output = input[0];
}
for (i = 1; i < input.length; i++) {
    output = (output + input[i]) - (output * input[i]);
}

所以我正在努力弄清楚如何遍历所有可能的可能性......并拥有类似的东西:(A 和 B 和 C 和 D)或(A 和 B 和 C)或(A 和 B 和 D)......等等......我希望你明白了。

Answer 1

这是一个简单的非递归解决方案，用于枚举至少包含 m 个元素的所有组合。

range = n => [...Array.from({length: n}).keys()]

mask = xs => b => xs.filter((_, n) => b & (1 << n))

at_least = n => xs => xs.length >= n

//

a = [...'ABCD']
m = 2

result = range(1 << a.length).map(mask(a)).filter(at_least(m))

console.log(result.map(x => x.join('')))

由于 JS 位算术限制为 32 位，因此这仅适用于 m < 32。