1

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
Olexandr Konovalov
  • 7,002
  • 2
  • 34
  • 72
Mare
  • 2,332
  • 1
    Search in this chapter: https://www.gap-system.org/Manuals/doc/ref/chap16.html. Also note the use of iterators in case the resulting list is very large. Another trick is to use index set i.e. for a set S find subsets of [1..Size(S)] and then form subsets of S one at a time. – Olexandr Konovalov Jun 25 '17 at 11:31
  • @AlexanderKonovalov The comment UnorderedTuples looks good. But it doesnt work when applied to my list [ <[ 1, 0 ]>, <[ 1, 1 ]>, <[ 0, 1 ]> ]. All that commands are also for sets instead of lists it seems. Is that a problem? – Mare Jun 25 '17 at 11:39
  • 1
    UnorderedTuples has repetitions - is that really what you had in mind? – Olexandr Konovalov Jun 25 '17 at 11:59
  • @AlexanderKonovalov no sorry, I mean just subsets. Had looked wrong. In all these commands there it seems I cannot input something like [ <[ 1, 0 ]>, <[ 1, 1 ]>, <[ 0, 1 ]> ] but only list of numbers? – Mare Jun 25 '17 at 12:03
  • <[ 1, 0 ]> is not a valid GAP input. How did you obtain it? – Olexandr Konovalov Jun 25 '17 at 12:05
  • I use the GAP package qpa. In fact those are modules over quiver algebras, displayed by their dimension vector. – Mare Jun 25 '17 at 12:07
  • Here is what I want to do with the subets: https://mathoverflow.net/questions/272984/finding-special-modules – Mare Jun 25 '17 at 12:08
  • I presume [ <[ 1, 0 ]>, <[ 1, 1 ]>, <[ 0, 1 ]> ] is stored in some GAP variable - you have to access it like I access s in my answer, instead of pasting the output. You may also try to print it with Print and see if that will be a valid GAP input. But anyway copying and pasting is error-prone, so write the code which avoids that. – Olexandr Konovalov Jun 25 '17 at 12:12
  • Let us continue this discussion in chat. – Mare Jun 25 '17 at 12:14

2 Answers2

3

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" ]
Olexandr Konovalov
  • 7,002
  • 2
  • 34
  • 72
  • Thanks, but that doesnt work when the elements of the list are modules coming from quiver algebras. Is that a bug? – Mare Jun 25 '17 at 12:11
  • I need to be able to reproduce the full example before making any further statements. Can you please edit your question and show how did you obtain the ist L? – Olexandr Konovalov Jun 25 '17 at 12:14
  • Apriori my suspicion is that to form a set it requires some way of sorting these modules, which is not defined by QPA. If you know that the list of modules does not have duplicates, you can use the "index set" approach as in the last example in my answer. – Olexandr Konovalov Jun 25 '17 at 12:16
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.

ahulpke
  • 18,416
  • 1
  • 21
  • 38