[r-t] Coset labeling

[Richard Smith]

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?

My current strategy is to use the lexicographically least 
one row from each coset Gr as its label and then compare 
labels.  In pseudo-code, we have a function:

   function label(r) {
     var x = back_rounds  // the maximum element of S_n
     foreach g in G {
       x = min( x, g*r )
     }
     return x
   }

and then test whether label(a) = label(b).

For the sake of argument, let's assume a row multiplication, 
a row comparison, and a row inversion all take 1 unit of 
time.  (That's a fairly good assumption.)  So the comparison 
of two labels costs 2|G|.

In most practical cases, it's possible to hand-craft a label 
function that's *much* quicker.  If G is S_{n-1}, locate the 
fixed bell and then fill the other bells in in order.  If 
it's A_{n-1}, do similarly and if necessary swap a pair to 
get the correct parity.  If it's S_m x S_n, find the 
position of the bells in the smaller cycle, reorder them if 
necessary and fix them, then drop the other bells in in 
order.

In each of these, we've replaced an O(|G|) algorithm with 
one that's O(1), and in doing so achieves a vast performance 
increase for things like G = S_3 x S_7 where |G| = 30240. 
But is it possible to write a general coset labelling 
algorithm that's O(1)?

I'm not willing to accept a lookup table with n! entries, 
mapping each element of S_n to a coset label.  But I may 
(just) be willing to accept a table with |G| entries.

Any thoughts?

RAS