Finding subsets of a list in GAP

Question

Is there a command in GAP to find all n-subsets of a list? So the input is a list and the output should be a list, which gives all n-subsets of the list in the input. Here an example of a list with 3 elements and wanting to find all sublists with 2 elements:

Input:

L:=[ <[ 1, 0 ]>, <[ 1, 1 ]>, <[ 0, 1 ]> ]

Output:

[ [ <[ 1, 0 ]>, <[ 1, 1 ]> ], [ <[ 1, 0 ]>, <[ 0, 1 ]> ], 
  [ <[ 1, 1 ]>, <[ 0, 1 ]> ] ]

Here the error I get when using the combinations command:

gap> L;
[ <[ 1, 0 ]>, <[ 1, 1 ]>, <[ 0, 1 ]> ]
gap> Combinations(L,2);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `<' on 2 arguments called from
Sort( mset ); at /home/rene/Schreibtisch/gap4r8/lib/combinat.gi:235 called from
<function "Combinations">( <arguments> )
called from read-eval loop at line 157 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue

Answer 1

You can use combinations as documented in this chapter.

For example:

gap> s:=["A","B","C"];
[ "A", "B", "C" ]
gap> Combinations(s,2);
[ [ "A", "B" ], [ "A", "C" ], [ "B", "C" ] ]

Generating the list of all combinations may be expensive, but you can iterate over them instead:

gap> for x in IteratorOfCombinations(s,2) do
> Print(x,"\n");
> od;
[ "A", "B" ]
[ "A", "C" ]
[ "B", "C" ]

Also, you can form combinations of indices instead of combinations of elements of the set itself, for example:

gap> for x in IteratorOfCombinations([1..Size(s)]) do
> Print(s{x},"\n");
> od;
[  ]
[ "A" ]
[ "B" ]
[ "C" ]
[ "A", "B" ]
[ "A", "C" ]
[ "B", "C" ]
[ "A", "B", "C" ]

Answer 2

The error message you got:

Error, no 1st choice method found for `<' on 2 arguments called from

indicates that the problem is with comparison. I suspect that qpa simply has no method for this comparison installed. (The reason for this being a problem is that Combinations first tests for duplicate entries amongst the arguments.) The easiest way to deal with it is probably to first creates sets of the index positions and then construct subsets. That is:

gap> L:=["A","B","C","D","E"];
[ "A", "B", "C", "D", "E" ]
gap> subsets:=Combinations([1..Length(L)],2);
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ],
  [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ]
gap> subsets:=List(subsets,x->L{x});
[ [ "A", "B" ], [ "A", "C" ], [ "A", "D" ], [ "A", "E" ], [ "B", "C" ],
  [ "B", "D" ], [ "B", "E" ], [ "C", "D" ], [ "C", "E" ], [ "D", "E" ] ]

This way you do not need to compare the elements of L themselves.