Problem
Given a vector of bools of length n
I wish to compute the logical and over all subsets up to length k
.
By logical and I mean that for a subset to give true
all of its elements must be true
.
Example:
With a boolean vector of 3 elements (indexes below each for reference below)
v = [true, true, false]
i = 0 1 2
The intended result for all subsets (i.e. up to k = n
):
result = [true, true, false, true, false, false, false]
i.e 0 1 2 0&1 0&2 1&2 0&1&2
where the true
at 01
is the result of true & true
from the 0
and 1
indices in the original vector.
If we limit up to k = 2
the intended result is:
result = [true, true, false, true, false, false]
i.e 0 1 2 0&1 0&2 1&2
The order of the output need not be this one.
What I want
I want an algorithm that will not perform more operations than it needs to specify the entire result. Reducing the number of operations should lead to improved performance.
My current approach is to iterate the combinations and subset the vector with each and reduce it via logical &
. But this is very wasteful as for 012
I recompute the result of 01
... There must be a better algorithm but I am having no success.