[GAP Forum] Computing "canonical" subsets

[Mikhail Klin]

Dear Gordon,
Probably this paper below may be somehow of help:

Pech, Christian; Reichard, Sven. Enumerating set orbits. Algorithmic 
algebraic combinatorics and Gröbner bases, 137–150, Springer, Berlin, 
2009.

As far as I am aware, Christian is holding some GAP programs,
related to this paper.

Regards,
Misha

********************************************************************

Dr. Mikhail Klin
Department of Mathematics 
Ben-Gurion University of the Negev
P.O.Box 653, Beer Sheva 84105, Israel
Tel: (0)8/6477-811  (office)
Fax: +972-(0)8/6477-648
e-mail: klin at cs.bgu.ac.il

On Wed, 12 Jan 2011, 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
>