[GAP Forum] efficient hamming distance computation

[Dmitrii (Dima) Pasechnik]

On 17 January 2013 15:52, A L <group.compute at gmail.com> wrote:
> Hello,
>
> For a project, I need to compute the minimal Hamming distance between a
> fixed permutation and a (large) permutation group.
it would be good to know how large the group can be, and what is its degree n.


> 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).

Note that if H is your group and g your permutation, then the Hamming
distance d(H,g) between H and g equals d(H,HgH), for HgH the double
coset of H in <H,g>, or in S_n, does not matter.
(This holds as d(f,g)=d(hf,hg)=d(hfh',hgh') for any f,h,h' in H.)
So you might begin by trying to find a "nicer" element in Hg.
E.g. you might want to find such an element with maximum (or just
large) number of fixed points. Then the pointwise stabilizer of these
points in H will contain the closest to g element, as far as I can
see.
Another point of view might be useful if you can construct the set of
double cosets of H in S_n. Then you can create a graph structure on
them using transpositions: H is connected to HtH for a transposition t
not in H (and so for any g in HtH one has d(H,g)=2, for g in Htt'H one
would have d(H,g)=3 or 4,... ), etc.

Perhaps there are even better methods for your problem: indeed,
computing d(,) seems to be an extension of a procedure to check
whether g is in H, and this is studied very extensively.

Seems to be a natural and interesting problem, IMHO!

HTH,
Dmitrii


>
> 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

CONFIDENTIALITY:This email is intended solely for the person(s) named and may be confidential and/or privileged.If you are not the intended recipient,please delete it,notify us and do not copy,use,or disclose its content.

Towards A Sustainable Earth:Print Only When Necessary.Thank you.