Btukfyl

I've been struggling for a little while to find or figure out algorithm.

The task:
Basically, I have an array of probabilities:

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

Let's name these inputs accordingly to: A, B, C and D.

And I also have a variable "m", which can tell me how many of these things needs to happen in order to get the result.
For example:

var m = 2;

This variable m is telling me that the event will happen if any of those two (or more) probabilities will happen.

So in this case, for event to happen, all possible ways for event to happen is:

ABCD
ABC
ABD
BCD
AB
AC
AD
BC
BD and CD

Now I need to calculate their probabilities, which I already have algorithms to calculate AND and OR (where input is just a probabilities array).

AND:

if (input.length > 0) {

    output = 1;

}

for (i = 0; i < input.length; i++) {

    output = input[i] * output;

}

OR:

if (input.length > 0) {

    output = input[0];

}

for (i = 1; i < input.length; i++) {

    output = (output + input[i]) - (output * input[i]);

}

So I am struggling on figuring out how to loop through all possible possibilities... And to have something like:
(A and B and C and D) or (A and B and C) or (A and B and D)... and so on... I hope you get the idea.

You could get the combinations of the wanted array with a minimum of two by using a recursive function which gerates all possible combinations.

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

Here's a simple non-recursive solution to enumerate all combinations with at least m elements.

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('')))

Since JS bit arithmetics is limited to 32 bits, this only works for m < 32.

You could go over all combimations of 2 elements (AB, CD etc.) with two nested loops:

 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

    }

  }

}

for at least m elements that can be generalized with a nested generator that generates an array of indices ([0, 1], [0, 2], [1, 2], [0, 1, 2]):

 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];

  }

}

Now for every combination, we just have to multiply the probabilities and add them up:

 let result = 0;



 for(const combination of combimations(input.length, m))

   result += combination.reduce((prev, i) => prev * input[i], 1);