[GAP Forum] Computing "canonical" subsets

[Hebert Pérez-Rosés]

Dear Gordon,

I'm not sure that I understand your problem correctly, but I will tell you
what I think, and you tell me if that's a (possible) answer to your
question:

If you can define a total ordering on the set of k-subsets, then the
canonical form of a particular k-subset A is the smallest k-subset B in the
G-orbit of A. Now you can generate all possible k-subsets in increasing
order, and for each new k-subset A, you don't have to compare it with every
previous one: you just have to compute the G-orbit of A, and check whether
there is a k-subset C in the G-orbit of A, that is smaller than A. In that
case, you can be sure that A has been considered before, and you can discard
it.

At first sight this looks more efficient than the other approach, but I
cannot guarantee that :-).

Best regards,
Hebert.



2011/1/12 Gordon Royle <gordon at maths.uwa.edu.au>

> 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
>