[r-t] Coset labeling
Alexander Holroyd
holroyd at math.ubc.ca
Fri Mar 30 22:30:52 UTC 2012
I think the following paper may well solve the problem Richard Smith asked
a while ago. Unfortunately there doesn't seem to be a free version
available that I can find, although those with a university library access
can easily download it.
Jerrum, Mark
A compact representation for permutation groups.
J. Algorithms 7 (1986), no. 1, 6078.
"A data structure is presented which allows an arbitrary permutation group
of degree n to be represented in O(n^2) space. An algorithm is provided
which, given a permutation group specified in the usual way as a set of
generators, constructs the proposed representation in time O(n^5). The
data structure supports fast membership testing, and is more economical
than those previously suggested, both in terms of its size and the time
required for its initialisation. Essential use is made of the proposed
data structure in an efficient algorithm for generating systems of coset
representatives; this algorithm may be used to solve certain instances of
the so-called `isomorph rejection' problem.''
-------
[r-t] Coset labeling
Richard Smith richard at ex-parrot.com
Sun Nov 20 00:30:35 GMT 2011
A quick question for the more mathematically-minded people
on the list. If G is a subgroup of the extent on n bells
(S_n), and a and b are two rows, what is a good algorithm
for determining whether a and b are in the same right coset
of G?
More information about the ringing-theory
mailing list