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

Question

我一直在努力寻找或找出算法。

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

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

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

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

var m = 2;

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

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

ABCDABCABDBCDAB交流公元BCBD和CD

现在我需要计算它们的概率，我已经有了计算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.

Answer 2

通过使用递归函数生成所有可能的组合，您可以获得所需数组的组合，其中至少有两个。

function getC(array, min) {
function iter(i, temp) {
var t = temp.concat(array[i]);
if (i === array.length) return;
iter(i + 1, t);
iter(i + 1, temp);
if (t.length >= min) {
result.push(t);
}
}

var result = [];
iter(0, []);
return result;
}
var input = [0.1, 0.2, 0.3, 0.1];
console.log(getC(input, 2).map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

您可以使用两个嵌套循环遍历2个元素(AB、CD等(的所有组合：

for(let i = 0; i < input.length; i++) {
for(let j = i + 1; j < input.length; j++) {
// possible combination: i and j
for(let k = j; k < input.length; k++) {  
// possible combination: i, j, k
// and so on
}
}
}

对于至少可以用生成索引数组([0, 1], [0, 2], [1, 2], [0, 1, 2](的嵌套生成器来概括的m元素：

function* combinations(length, m = 1, start = 0) {
// Base Case: If there is only one index left, yield that:
if(start === length - 1) {
yield [length - 1];
return;
}
// Otherwise go over all left indices
for(let i = start; i < length; i++) {
// And get all further combinations, for 0 that will be [1, 2], [1] and [2]
for(const nested of combinations(length, m - 1, i + 1)) {
// Yield the nested path, e.g. [0, 1], [0, 1, 2] and [0, 2]
yield [i, ...nested];
}
// If the minimum length is already reached yield the index itself
if(m <= 1) yield [i];
}
}

现在，对于每一个组合，我们只需要乘以概率并将其相加：

let result = 0;
for(const combination of combimations(input.length, m))
result += combination.reduce((prev, i) => prev * input[i], 1);