[GAP Forum] efficient hamming distance computation

[Nagy Gabor]

Hi,

I am used to do a lot of calculation with distances of permutations.

According to me,

NrMovedPoints(a/b)

is very efficient to compute d(a,b).

More difficult is to find the element b of G which is "closest" to a. I 
would do it rather straightforward.

G:=PGL(2,53); Size(G);

closest:=function(G,a)
     local md,x,b;
     md:=NrMovedPoints(G); b:="";
     for x in G do
         if NrMovedPoints(x/a)<md then
             md:=NrMovedPoints(x/a);
             b:=x;
         fi;
     od;
     return b;
end;

a:=Random(SymmetricGroup(NrMovedPoints(G)));
b:=closest(G,a);
time;

You can check the result by

NrMovedPoints(a/b);
Collected(List(G,u->NrMovedPoints(a/u)));

I hope this helps.

Bye,

Gabor


On 01/17/2013 08:52 AM, A L wrote:
> Hello,
>
> For a project, I need to compute the minimal Hamming distance between a
> fixed permutation and a (large) permutation group. What is the "correct"
> way to do this in GAP? I am looking for the most efficient method, both for
> the Hamming distance computation between individual elements, as well as
> ways to avoid brute-force comparison with each element in the group
> (perhaps utilizing information about the group's structure).
>
> Any help or pointers/references would be appreciated. I am new to GAP and
> have tried my best to wade through the extensive documentation.
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>