[r-t] Parity

[Fred Bone]

On 23 Jun 2007 at 17:59, Robin Woolley said:

> More than 30 years ago (!), the late Tony Carter (of Luton & Harpenden) 
> published an article dealing with the material given in Fred Bone's reply. I 
> have not been able to find my copy so have done my best to reconstruct the 
> contents. Please bear with me if any errors have crept it over that time, 
> but see what you can make of it.
> 
> First. It is not necessary to sort the changes to derive the 'factorial 
> index'. It can be done straight from the change. For example, on 6 bells, 
> the change 213456 must give the index 120. To obtain the index, we reduce 
> each bell by the number of bells smaller than it to its left. So 213456 
> becomes 211111, but as Fred notes, we require rounds to be the zeroth index 
> so reduce the result by one in each posiiton to give 100000. On mutliplying 
> by the appropriate factorial, one gets the 'lexicographical-order' number.

A more direct approach (to my mind) is to count the smaller bells on the 
right. (Proof: for any given bell, k, there are (k-1) smaller bells. If l 
of these are to the left and r to the right, then r = k-1-l, which is 
exactly the number obtained above).

Using this method, as you say, you get the factorial base representation 
first, so the parity follows trivially. However, I understood the OP to 
have the permutation index already and to want a way to derive the parity 
from that.

BTW the representation you give for the factorial base will always end in 
zero (the multiple of 0!). I prefer to write it without that, i.e. with 
the last digit being the multiple of 1!, which amounts to ignoring the 
final bell in the calculation (it having none after it ...), hence I 
would write the factorial base representation

> Second. Tony told me that the above was known long before he published the 
> article. He claimed the following extension. It is possible to generate the 
> next factorial index *directly* from the previous using place notation only. 
> The advantage of this is that one only needs to evaluate the actual change 
> for the changes you require. Checking is done by checking the index which, 
> inter alia, needs only one 'bit' - useful on a 48k Spectrum.
> As far as I can remember/see, the algorithm goes as follows:
> 
> Consider 213456, index 100000 followed by 14 then 'x' place notations. The 
> change are 231465 and 324156 respec. which (seem) to have indices 110010 & 
> 211011. The algorithm (seems) to be this. In swapping AB, then i if A=>B, we 
> have B+1.A else B.A

The last digit (in 6-digit notation) is always zero. 324156 is perm-index 
270 = 21100[0]. It is (fairly) obvious that restoring 56 to their 
previous position (which is what 14.x does) must restore their 
corresponding digits, given that they come last.

This algorithm (which I think you have the wrong way round, even in your 
subsequent e-mail) holds only for neighbouring bells, i.e. you can only 
apply it one change at a time. For example,
324156 gives 21100[0] = 270
624153 gives 51201[0] = 637

Writing A,B for the (two successive) digits in factorial base and a,b for 
the corresponding bell numbers,
A>B if and only if a>b
so that the swap (a,b)->(b,a) results in
(A,B)->(B,A-1) if A>B, and
(A,B)->(B+1,A) otherwise.

For example, 
231465 gives 110010 (145)
324156 gives 211000 (270)