On 17 January 2013 15:52, A L <group.comp...@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@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. _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
