[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