We describe an algorithm for finding a canonical image of a set of
points under the action of a permutation group. Specifically if we
order images by sorting them and ordering the resulting sequences
lexicographically, we find the first image. This has applications to
combinatorial and other search problems, allowing isomorphic results
to be eliminated more efficiently.
We give worst-case asymptotic running time estimates and practical
results obtained with a GAP implementation.
|