1

I have a list and a function on the elements on this list. I want to define an equivalence relation on this list by saying that two elements are equivalent if the function applied to those elements gives the same results. Is there a way to obtain in GAP the euivalence classes (so the result should be a list of lists corresponding to the equivalence classes). Example: The list is

[ [ 2, 2, 2, 1 ], [ 3, 2, 2, 1 ], [ 2, 3, 2, 1 ], [ 3, 3, 2, 1 ], [ 4, 3, 2, 1 ] ]

and the function $f$ is taking the Maximum of the number of such an element. Thus for example $f([ 3, 2, 2, 1 ])=3$. The equivalence classes are in this example :

-[ 2, 2, 2, 1 ]

-[ 3, 2, 2, 1 ], [ 2, 3, 2, 1 ], [ 3, 3, 2, 1 ]

-[ 4, 3, 2, 1 ]

Mare
  • 2,332

1 Answers1

1

If you can hold all objects in memory, it probably is easiest to once apply the function to get a list of values, then get equivalence classes of indices by (set of) values, and then get the lists. This can be done conveniently with the List and Filtered operations. In your example

gap> l:=[ [ 2, 2, 2, 1 ], [ 3, 2, 2, 1 ], [ 2, 3, 2, 1 ], [ 3, 3, 2, 1 ], [ 4,...
[ [ 2, 2, 2, 1 ], [ 3, 2, 2, 1 ], [ 2, 3, 2, 1 ], [ 3, 3, 2, 1 ],
  [ 4, 3, 2, 1 ] ]
gap> v:=List(l,Maximum);
[ 2, 3, 3, 3, 4 ]
gap> idx:=List(Set(v),x->Filtered([1..Length(v)],y->v[y]=x));
[ [ 1 ], [ 2, 3, 4 ], [ 5 ] ]
gap> List(idx,x->l{x});
[ [ [ 2, 2, 2, 1 ] ], [ [ 3, 2, 2, 1 ], [ 2, 3, 2, 1 ], [ 3, 3, 2, 1 ] ],
  [ [ 4, 3, 2, 1 ] ] ]

Note that if the values of the function are algebraic structures, and not just numbers, it can be worth to replace Set by Unique in line -5.

ahulpke
  • 18,416
  • 1
  • 21
  • 38
  • Thanks, this looks pretty cool. the second step v:=List(l,Maximum); does not work if the Function depends on two arguments, like for example CoxeterPolynomial(NakayamaAlgebra(-,GF(3)) instead of Maximum, where - is the thing where I want the list to be put in. Is there a trick to fix this? (expect to apply NakayamaAlgebra(-,GF(3)) before, which I can do and it is also an option) – Mare Aug 25 '17 at 18:29
  • 1
    If the function takes further arguments you can use the inline function notation to wrap it into a one-argument function,e.g. replace Maximum by x->BlaBla(FooBar(x,GF(3),99)) – ahulpke Aug 25 '17 at 20:17