[GAP Forum] Fast Orbit Computation for Custom Objects?
Sven Reichard
Sven.Reichard at tu-dresden.de
Fri May 17 09:53:55 BST 2013
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Dear Forum,
I have the following data:
- - A permutation group G;
- - a set of objects obj;
- - an action function.
I would like to get the following:
- - The union D of the orbits of obj under G (not necessarily sorted);
- - the action H of G on D;
- - orbit representatives.
What I do is the following:
orbits := Orbits(G, obj, action);
representatives := List(orbits, Representative);
D := Union(orbits); # sorted to accelerate the next step
H := Action(G, D, action);
This works well when action is a standard action such as OnSetsSets.
However, for custom actions this can be very slow, suggesting that
different algorithms are used. (In some of my examples, D has a
million elements.)
Is there a way in GAP4 to accelerate this process, for example by
providing hash functions? In GAP3 there existed a solution in the
contributed file coco.grp by Theißen based on work by Faradzev et al.
The question is whether there is a better way than porting that file
to GAP4.
Regards,
Sven Reichard.
- --
Institut für Algebra
TU Dresden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEVAwUBUZXwI2FjB3Gki4XVAQJrDgf+IdzNftD5zutKuXm/7vOWQhSOe6ZdeJ8p
N+FWYHgXYuHfHPrXquv/iUzVKRaADu01+enk/T9sYIr6oEorcAO5GS0uh/5yhBSq
IqL5jsvkyCbrW3jN8sjGUZanGw5z81cjx5VoigYuaON8VMB8qGMQ6w20B+0XdTss
29YZJZz1r2JMNB/Lfx7iiqHCRalfK1+qnnvimro404H2jc+sjvGH83nh6z3uZLy4
eaDBOaJgI2Uz8Nz3SL2KBEzhQ02Ipem3jEC37izS9Or20zotcog/G3v0uLsy10/G
y7mcQ0lfhxH4PwQ1OpTbvFD4WHNQ1riMTmG5qtZgP9d7uymKBssmMA==
=JAOJ
-----END PGP SIGNATURE-----
More information about the Forum
mailing list