Dear GAP-Forum, I must point out that this SmallestImageSet function, which determines the lex-least set in the G-orbit of a subset S of X (where G is a permutation group on the finite set X) was designed and written by Steve Linton. This extremely useful function (which does not need to compute the G-orbit of S) is used internally within GRAPE, and is not documented.
For more information, see pkg/grape/lib/smallestimage.g in your GAP distribution, and also the article: Steve Linton, Finding the smallest image of a set, Proceedings of ISSAC '04, ACM, New York, 2004. I am hoping that, in due course, Steve will either make this excellent function (and certain variants he has devised) into a package or part of the main distribution of GAP. You may also be interested in: Enumerating Set Orbits, by Christian Pech and Sven Reichard, in Algorithmic Algebraic Combinatorics and Gröbner Bases, Springer, 2009, Part 1, pp. 137-150. and in: On classifying objects with specified groups of automorphisms, friendly subgroups, and Sylow tower groups, by Leonard H. Soicher; Research Report, 2008, available at http://designtheory.org/library/preprints/friendly.pdf Regards, Leonard Soicher On Wed, Jan 12, 2011 at 01:21:43PM +0100, Mathieu Dutour wrote: > As far as I know, once you have a backtracking algorithm > for equivalence/stabilizer, then you have also an algorithm > for canonical representative. > > But GAP does not provides such functionalities ... > > However, for the special action "OnSets", there is a function > "SmallestImageSet" available from the GRAPE package that does > the job. > > Mathieu > > On Wed, Jan 12, 2011 at 08:04:13PM +0800, Gordon Royle wrote: > >> Dear Gapsters.. > >> > >> Consider the following generic problem... given a permutation group > >> G acting on a set X, I have a (potentially) large collection of > >> k-subsets of X and wish to keep only one representative of each > >> G-orbit on k-subsets. > >> > >> GAP can tell me if two k-subsets are equivalent under G using > >> RepresentativeAction and so in principle, I can build up a list > >> by starting with the first one, then testing to see if the second > >> is equivalent to the first and keeping it only if it is not, and > >> so on. This works, but each new one requires one more test than > >> the previous one and things rapidly become unmanageable. > >> > >> For winnowing large lists of graphs, the standard procedure is > >> not to test them pairwise but rather to compute a "canonically > >> labelled" version of each input graph and then simply throw out > >> the duplicates... > >> > >> Is there any way of computing a "canonically labelled" version > >> of each k-subset? Or is this well known to be more difficult > >> than computing equivalence? > >> > >> Thanks > >> > >> Gordon > >> _______________________________________________ > >> Forum mailing list > >> Forum@mail.gap-system.org > >> http://mail.gap-system.org/mailman/listinfo/forum > > _______________________________________________ > Forum mailing list > Forum@mail.gap-system.org > http://mail.gap-system.org/mailman/listinfo/forum _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
