# [r-t] Parity

Richard Smith richard at ex-parrot.com
Thu Jun 21 12:39:06 UTC 2007

```Leigh Simpson wrote:

> I was hoping to find a quick way to find the parity
> based on finding an index of the row and analysing
> that index. Since the parity doesn't behave nicely
> that avenue seems prohibitive.

If you want a mapping from rows to integers, and an
efficient way of finding the parity of the row simply from
the integer, how about using Plain Changes to order the
rows?  That way the rows alternate in parity, and if you
number them 0 ... n!-1, the even rows have even parity, and
the odd rows odd parity.

1234 ->  0 +    1342 ->  8 +    1423 -> 16 +
2134 ->  1 -    3142 ->  9 -    4123 -> 17 -
2314 ->  2 +    3412 -> 10 +    4213 -> 18 +
2341 ->  3 -    3421 -> 11 -    4231 -> 19 -
3241 ->  4 +    4321 -> 12 +    2431 -> 20 +
3214 ->  5 -    4312 -> 13 -    2413 -> 21 -
3124 ->  6 +    4132 -> 14 +    2143 -> 22 +
1324 ->  7 -    1432 -> 15 -    1243 -> 23 -

Generating the rows in this order is probably more efficient
than generating the rows in lexicographic order.  (I say
probably because it depends exactly what 'primitive'
operations you have available and their relative
efficiencies.)

Like most such things, though, there is an efficency trade
off.  Three (mutually related) important operations are:

1. mapping an arbitrary row to an integer;
2. mapping an arbitrary integer back to its corresponding row;
3. ordering a pair of rows.

For the lexicographic order, these are obvious (see for
example the Ringing Class Library for an implementation).
For plain changes, however, they're slightly more subtle;
but it's perfectly possible to devise algorithms for these
operations by exploiting the recursive nature of the