Dear Ruben,
first a general remark: GAP represents a permutation pi internally as a list,
which at position i has the value for i^pi. That means that the memory used to
store a permutation scalers linearly with the largest point moved by it. If
this is less than 2^16, then 2 bytes are used per point, else 4 bytes. You can
see this here:
gap> MemoryUsage( (1,2) );
36
gap> MemoryUsage( (1,20000) );
40032
gap> MemoryUsage( (1,200000) );
800032
So the third transposition takes 800 kb RAM. If you square it, GAP has to read
all that memory -- that alone of course already will be much smaller than
reading the memory for the transposition (1,2). In addition, depending on how
much memory your system has resp. you gave GAP, it has now to perform many more
garbage collections to make room for these humongous permutations.
So, following Dima's good suggestion to relabel is key (while there has been
some talk about adding a "sparse" permutation representation, this does not yet
exist, and I also kind of would consider it a band aid; it's better to fix the
underlying problem, i.e. avoid needless use of gigantic point values).
Now to your specific problem:
> On 27 Mar 2018, at 15:24, Sanchez Garcia R. <r.sanchez-gar...@soton.ac.uk>
> wrote:
>
> Thank you Dmitrii.
>
> I tried your suggestion but the replacement of generators takes at least as
> long as computing the orbits in the original permutation group (code below).
>
> Listing all the integers before the permutation won’t help either, as most
> integers 1 to n appear at least once.
That sentence confuses me. Your originally question sounded as if the set of
moved points for your permutation groups was small; this sentence now sounds as
if it was not (and in that case, things are hopeless).
>
> This is what I tried:
> #produce small generators
> mp := MovedPoints(gens);;
> l := Length(mp);;
> p := ();;
> for i in [1..l] do
> if mp[i] > l then
> p := p * (i,mp[i]);;
> fi;
> od;
> gens := OnTuples(gens,p);;
Don't do that! Remap the permutations directly:
gap> gens:=[(10000,20000),(30000,40000)];
gap> mp := MovedPoints(gens);;
gap> smallgens:=List(gens, g -> Permutation(g, mp));
[ (1,2), (3,4) ]
# perform orbit computation
gap> small_orbs:=Orbits(Group(smallgens));
[ [ 1, 2 ], [ 3, 4 ] ]
# map back to the original numbers
gap> orbs:=List(small_orbs, o->mp{o});
[ [ 10000, 20000 ], [ 30000, 40000 ] ]
Hope that helps,
Max
_______________________________________________
Forum mailing list
Forum@gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum
