[r-t] Coset labeling

[Graham John]

RAS wrote:
 
> I'm not sure what you're suggesting

OK, here is an attempt to explain better. I don't have the benefit of a
maths degree, or even maths A-Level, so please excuse my lack of familiarity
with the theory, and avoidance of mathematical expressions I am unfamiliar
with. 

For normal proving, I use the C# algorithm below (a method of the Row class)
to generate a unique number between 0 and !stage for a row. 

private ulong GetProvingNumber()
{
	//Proving numbers for stages greater than 20 are too large to fit in
a long
     if (_stage.Bells > 20)
         return 0;
	//Use the (zero-based) positions of the bells in the row, rather
than the row itself
     Row rowpos = BellPositions(); 
	//Calculate proving number for the row
	ulong pnumber = 0;
	for (int i = 0; i < _stage.Bells - 1; i++)
     {
		//Calculate a factorial multiplier for the bell position
		ulong r = (ulong)rowpos[i];
		for (int j = i; j >= 0; j--)
		{
			//Reduce the multiplier by 1 for each bell position
lower than it already processed
			if (rowpos[j] < rowpos[i])
				r -= 1;
		}
		//Then multiply by the factorial for its position and add to
sum
		pnumber += r * factorial[_stage.Bells - 1 - i];
	}
	//Return a unique number for the row between 0 and factorial stage
	return pnumber;
}

You will note that it uses the position of the bells in the row, rather than
the row itself. In compositions on higher numbers, the back bells are much
more likely to be in fixed relative positions than the front ones, so when
truncating the proving number into a hash, this substantially reduces the
probability of collisions. For a generic proof, I allocate 64K to a proving
table, and use the lowest 16 bits of the proving number as a hash into it.
This means that up to ten bells can proved uniquely, and up to 20 bells
using hashing. 

The simplest way to achieve the O(1) efficiency Richard is looking for is to
transpose each parthead (for compositions, or leadhead for methods) by each
row and calculate the proving number for the lowest transposition. This
technique we have both used before, albeit with further optimisation from
hand-crafting specific cases into the proving number algorithm itself. The
efficiency gain here is not in the proving, which is fairly small, but in
the elimination of branches of a search tree when carrying out exhaustive
search for methods or compositions. 

If we take an example leadhead/parthead of 135724680T9E there are 5 cycles
[1][235][467][8][90ET] and 12 parts. The above technique is fast, as all
parts are proved simultaneously, but it uses 12 times more memory than is
really required for a unique proving table. 

I assert that it is possible to create a generic algorithm which produces a
unique proving number = !stage / no_of_parts. Again it is easier to work
with the positions of the bells rather than the row itself, as it separates
the cycles. By transposing the digits, adjusting the multiplier used for
each position and the factorials each is multiplied by to contribute to the
proving number sum, the redundant number ranges could be eliminated. 

Having said that, I think producing such an algorithm is far from trivial.
Moreover, I feel that the extra processing required to achieve this would be
far greater than the additional processing involved in dealing with the
small number of hash collisions when using the simpler technique. If a 64K
proving table were used for the 12-bell example above, the probability of a
hash collision would be reduced from 1 in 132 to 1 in 11, yet the processing
overhead would be incurred on every row. 

Graham