Removing all supersets of a given subset from a powerset?

asked 2021-01-16 07:24:27 +0200

Alasdair gravatar image

First, my apologies if this is a trivial question. I am working through the powerset of a finite set of positive integers. I also have a predetermined value V. The idea is that as soon as I find a subset S whose elements sum to V or more, I want to remove all supersets of S, so that I don't have to test them. For example, suppose my set is {10,9,6,5} and V=16. When I find S = {10,9} has the property of I want, I can remove all supersets of {10,9} from further consideration. The final result will be just three subsets: {10,9}, {10,6}, and {9,6,5}.

I can do this "by hand" as it were, but is there a method already built-in for this? I've been fiddling around with lattices and posets and lower covers, but I can't get any of the methods to work.

I'd welcome any advice!

edit retag flag offensive close merge delete


Maybe using RecursivelyEnumeratedSet ?

FrédéricC gravatar imageFrédéricC ( 2021-01-16 08:35:41 +0200 )edit

Adding elements one by one, you need to define a successor function : see

FrédéricC gravatar imageFrédéricC ( 2021-01-16 11:57:59 +0200 )edit