1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ I don't understand what you're asking for. What do you mean by "the effective & over all subsets up to length $k$" of an $n$-bit vector? Please try to give a precise definition rather than just examples, not least because I can't work out what's happening in your examples, let alone trying to deduce the general case from them. Isn't the "and" of the variables just going to be false, unless all the variables are true? Breaking it down into subsets doesn't seem to affect this. $\endgroup$ – David Richerby Oct 4 '15 at 17:58
  • $\begingroup$ What exactly do you want? If you want all subsets it's going to be very wasteful regardless of how you do it because there are just very many subsets. $\endgroup$ – Tom van der Zanden Oct 4 '15 at 17:58
  • $\begingroup$ @DavidRicherby I have updated my question to hopefully be more clear. please let me know how else I can clarify $\endgroup$ – Lars Quinnn Oct 4 '15 at 18:26
  • $\begingroup$ @TomvanderZanden Edited to clarify. I would like an algorithm that doesn't compute bitwise and if a subset of its elements have already been computed to false. (kind of like a cumulate all but over all subsets) $\endgroup$ – Lars Quinnn Oct 4 '15 at 18:28
  • $\begingroup$ If just one element of the array is false, it will appear in one subset and make that one false, thus you just have to check for that, which is $O(n)$. $\endgroup$ – vonbrand Oct 5 '15 at 0:54
1
$\begingroup$

You can do this without computing the logical AND's at all: you can enumerate all subsets that consist entirely of "true" and enumerate all subsets that contain at least 1 "false".

First, enumerate all subsets of length $k$ with all "true".

Then, enumerate all subsets of length $k$ that contain the first occurrence of "false" in the vector.

Then, enumerate all subsets of length $k$ that contain the second occurrence of "false" but not the first.

Etc...

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.