Powerset filter_map?

[JeremyRubin]

it would be a really useful API to have a powerset + filter api whereby we can express a predicate such that if S is subset of U, and P(S) = false, then subsets of S are not visited efficiently. Example usage:

let t = 100;
v.powerset().filter(|v| v.iter().sum() < t);
v.powerset_subset_filter(|v| v.iter().sum() < t);

You can't implement this "the obvious way" because, for example:

[1,2,3,4] filter for > 6

[1,2,3,4] -> sum([1,2,3]) fails [1,2,3,4] -> sum([1,2,4] ) succeeds

[1,2] is a subset of [1,2,3] and [1,2,4].

I'm not aware of an algorithm that solves this neatly, although one could imagine a memoization whereby you have a memo table of supersets queryable by a subset and you stop iteration if a superset of you is marked invalid. I'm not aware of such a data structure, however.

[phimuemue]

Hi there, I am not sure if I completely understand your proposal. Could you clarify it (preferrable in mathematical terms and with a full example so that we make sure that we're on the same page)? Do you essentially mean that for each set U produced by powerset, the algorithm should check whether there exists a subset S of U with P(S)==false, and - if so - discard U?

[JeremyRubin]

yeah I guess I think you want both behaviors.

For a full example you can see https://rubin.io/bitcoin/2021/12/22/advent-25/ (LOL). Basically I want to compute all the minimal subsets of members that have enough voting power to pass a vote. We don't need non minimal votes since if [Alice, Bob] can pass a vote, it's unrequired to have [Alice, Bob, Carol] represented as a key.

I think in math terms this comes out to something like

T := { s \in U : F(s) \and (\not \exists t \in T t != s \and t \subset s)}

T is the set of all subsets of U, such that for every element in T s, F(s) is true and there does not exits a strict subset t already.

you also want the inverse of this, where

T := { s \in U : F(s) \and (\not \exists t \in T t != s \and t \supset s)}

T is the set of all subsets of U, such that for every element in T s, F(s) is true and there does not exits a strict superset t already.

or in very plain english:

Find the biggest groups with this property and none of it's subsets (intersecting sets are OK).

Find the smallest groups with this property and none of their supersets (intersecting still OK).

The difference is basically iteration order, if you start with combinations(N) or combinations(1). But combinations is inelegant for this issue.

[Philippe-Cholet]

I sure would like the algorithmic challenge of doing this but this is simply a niche use we sure won't do. And after working combinations & Co we would not be able to be really efficient anyway (generate vectors for each item is slow, we don't have lending iterators).