[r-t] Coset labeling

[Alexander Holroyd]

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?