[GAP Forum] Power set

Thomas Breuer thomas.breuer at math.rwth-aachen.de
Thu Dec 21 09:04:42 GMT 2006


Dear GAP Forum,

D. Naidu wrote

> Let X be a finite set and let x be a fixed element of X.
> Is there any function in GAP that generates all subsets of X that contains x.

The function `Combinations' can be used to compute the power set
of a (not too large) set, see the GAP Reference Manual.

If one is interested only in those subsets of the given set X
that contain a prescribed subset Y, say,
then one can of course form the power set of the difference X \ Y,
and then consider the unions of these sets with Y.

Here is an example.

    gap> set:= [ 1, 2, 3, 4 ];;
    gap> elms:= [ 2 ];;
    gap> diff:= Difference( set, elms );;
    gap> Set( List( Combinations( diff ), x -> Union( x, elms ) ) );
    [ [ 1, 2 ], [ 1, 2, 3 ], [ 1, 2, 3, 4 ], [ 1, 2, 4 ], [ 2 ], [ 2, 3 ], 
      [ 2, 3, 4 ], [ 2, 4 ] ]

(Of course one can do this more cleverly;
for example, the entries in the list returned by `Combinations' are mutable,
so one could use `UniteSet' instead of `Union', and the final call of `Set'
could be replaced by a call of `Sort' for the list of unions.
This way one would avoid creating a lot of intermediate objects.)

All the best,
Thomas




More information about the Forum mailing list