[GAP Forum] Computing "canonical" subsets

[Mathieu Dutour]

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 at mail.gap-system.org
>> http://mail.gap-system.org/mailman/listinfo/forum