Obtaining a list up to cyclic shifts in GAP

Question

I have a list of lists in GAP, for example as follows: $L=[ [ 2, 2, 2, 2, 3 ], [ 2, 2, 2, 3, 3 ], [ 2, 2, 2, 4, 3 ], [ 2, 2, 3, 2, 3 ], [ 2, 2, 3, 3, 3 ], [ 2, 2, 3, 4, 3 ], [ 2, 2, 4, 3, 3 ], [ 2, 2, 4, 4, 3 ], [ 2, 2, 5, 4, 3 ], [ 2, 3, 2, 2, 3 ], [ 2, 3, 2, 3, 3 ], [ 2, 3, 2, 4, 3 ], [ 2, 3, 3, 2, 3 ], [ 2, 3, 3, 3, 3 ], [ 2, 3, 3, 4, 3 ], [ 2, 3, 4, 3, 3 ], [ 2, 3, 4, 4, 3 ], [ 2, 3, 5, 4, 3 ], [ 2, 4, 3, 2, 3 ], [ 2, 4, 3, 3, 3 ], [ 2, 4, 3, 4, 3 ], [ 2, 4, 4, 3, 3 ], [ 2, 4, 4, 4, 3 ], [ 2, 4, 5, 4, 3 ], [ 2, 5, 4, 3, 3 ], [ 2, 5, 4, 4, 3 ], [ 2, 5, 5, 4, 3 ], [ 2, 6, 5, 4, 3 ] ]$.

Question: Is there an easy command in GAP to obtain such a list up to cyclic shifts so that two elements of $L$ get identified in case they are cyclic shifts of each other?

So the input should be such a list L and the output a list $L'$ which contains all elements up to a cyclic shift.

For example, the two elements $[2,3,2,3,3]$ and $[2,3,3,2,3]$ should get identified because they are cyclic shifts of each other.

So in case we input $L=[[2,3,2,3,3],[2,3,3,2,3]]$ the output should be $[[2,3,2,3,3]]$. (It should give one representative of an equivalence class up to cyclic shift, it doesn't matter how this representative looks).

Answer 1

The task can be accomplished via user-defined GAP functions.

The following three functions will suffice . . .

• $\text{rot}(x)$
  • $x$ is expected to be a list.
  • Returns a copy of the list $x$, rotated to the right by $1$.

• $\text{canon}(x)$
  • $x$ is expected to be a list of comparable objects (e.g., integers).
  • Returns the rotation of the list $x$ which is lexicographically least.

• $\text{reduce}(L)$
  • $L$ is expected to be a list of lists of comparable objects.
  • Returns a list of canonical representatives of the elements of $L$.

Here's an implementation . . .

rot:=function(x)
    local n,a;
    a:=x[1];
    n:=Length(x);
    x:=x{[2..n]};
    Add(x,a);
    return x;
end;

canon:=function(x)
    local x0,x_min;
    x0:=ShallowCopy(x);
    x_min:=ShallowCopy(x);
    while true do
        x:=rot(x);
        if x=x0 then break; fi;
        if x<x_min then x_min:=ShallowCopy(x); fi;
    od;
    return x_min;
end;

reduce:=L->Set(List(L,canon));

a:=
[ 
   [ 2, 2, 2, 2, 3 ], [ 2, 2, 2, 3, 3 ], [ 2, 2, 2, 4, 3 ], [ 2, 2, 3, 2, 3 ], 
   [ 2, 2, 3, 3, 3 ], [ 2, 2, 3, 4, 3 ], [ 2, 2, 4, 3, 3 ], [ 2, 2, 4, 4, 3 ], 
   [ 2, 2, 5, 4, 3 ], [ 2, 3, 2, 2, 3 ], [ 2, 3, 2, 3, 3 ], [ 2, 3, 2, 4, 3 ], 
   [ 2, 3, 3, 2, 3 ], [ 2, 3, 3, 3, 3 ], [ 2, 3, 3, 4, 3 ], [ 2, 3, 4, 3, 3 ], 
   [ 2, 3, 4, 4, 3 ], [ 2, 3, 5, 4, 3 ], [ 2, 4, 3, 2, 3 ], [ 2, 4, 3, 3, 3 ], 
   [ 2, 4, 3, 4, 3 ], [ 2, 4, 4, 3, 3 ], [ 2, 4, 4, 4, 3 ], [ 2, 4, 5, 4, 3 ], 
   [ 2, 5, 4, 3, 3 ], [ 2, 5, 4, 4, 3 ], [ 2, 5, 5, 4, 3 ], [ 2, 6, 5, 4, 3 ]
];

b:=reduce(a);
[
   [ 2, 2, 2, 2, 3 ], [ 2, 2, 2, 3, 3 ], [ 2, 2, 2, 4, 3 ], [ 2, 2, 3, 2, 3 ],
   [ 2, 2, 3, 3, 3 ], [ 2, 2, 3, 4, 3 ], [ 2, 2, 4, 3, 3 ], [ 2, 2, 4, 4, 3 ],
   [ 2, 2, 5, 4, 3 ], [ 2, 3, 2, 3, 3 ], [ 2, 3, 2, 4, 3 ], [ 2, 3, 3, 3, 3 ],
   [ 2, 3, 3, 4, 3 ], [ 2, 3, 4, 3, 3 ], [ 2, 3, 4, 4, 3 ], [ 2, 3, 5, 4, 3 ],
   [ 2, 4, 3, 3, 3 ], [ 2, 4, 3, 4, 3 ], [ 2, 4, 4, 3, 3 ], [ 2, 4, 4, 4, 3 ],
   [ 2, 4, 5, 4, 3 ], [ 2, 5, 4, 3, 3 ], [ 2, 5, 4, 4, 3 ], [ 2, 5, 5, 4, 3 ],
   [ 2, 6, 5, 4, 3 ]
]