Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Removing all supersets of a given subset from a powerset?

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!