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 <gor...@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@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
