Problem with permutation cycles

[Martin Vladic]

Could you find algorithm (efficient) which finds all cycles for this
permutation:
(11,12,13,...,1n,21,22,23,...2n,...,m1,m2,m3,...,mn) -->
(11,21,31,...,m1,12,22,32,...m2,...,n1,n2,n3,...,nm) ?
[ Example: For (11,12,13,14,21,22,23,24) --> (11,21,12,22,13,23,14,24)
cycles are:
(11) (12,13,21) (14,23,22) (24) ].
(Or in another words: can you transpose matrix within same memory space?)

[Dave Rusin]

In article <61ge4d$t...@argos.tel.hr>,

Martin Vladic <mv3...@pinus.cc.fer.hr> wrote:
>Could you find algorithm (efficient) which finds all cycles for this
>permutation:

>(Or in another words: can you transpose matrix within same memory space?)

So you have an array A with elements labelled 1, 2, ..., m*n; you envision
these elements placed row by row (say) into a rectangular (m x n) array M1, so
that at location (i,j) in M1 you have placed array element number
j+n*(i-1) of A. Then you make a new array M2 (this time n x m) whose
(i,j) entry is M1(j,i). Finally you write these elements row by row into
a linear array B, placing the (i',j') element of M2 in entry
j'+m*(i'-1) of B. You want to know the new location of a generic array
element A(k) in B.

Well, you've got all the formulas now; you know there are indices (i,j) with
k=j+n*(i-1);
from these indices you deduce the new location in B to be
j'+m*(i'-1) = i+m*(j-1)=i-m+m*(k-n*(i-1))= m*k + (m*n-m) - i*(m*n-1)
Perhaps you didn't think of this as good enough since it's not expressed in
terms of k alone; you want the i to go away.

But this we can do: reading the formula mod m*n-1 shows the new location
to be congruent to m*k + (1-m). That's almost good enough, since there
are only m*n locations! All you need to do now is note that the first
and last elements of A remain first and last, respectively, in B.
In all other cases, we need only determine the residue of
f(k)=m*(k-1)+1 modulo m*n-1 which is in the range [2, m*n-1].
That is, element A(k) is placed in location B(f(k)).

Now it's easy to get the cycle structure, too. Note that with this
presentation, it's easy to iterate f: f^r (k) = m^r*(k-1)+1. Since
m is invertible mod m*n-1, f^r(k)=k iff (m^r - 1)*(k-1) = 0 mod m*n-1.
In particular, the order of f (the l.c.m. of the cycle lengths) is
the order of m mod m*n-1.

Here are some examples. If m=n, we need the order of m mod m^2-1,
which is clearly 2. The permutation has order 2, and the length of
every cycle is 2 except for the cycles involving elements k with
(m^1 - 1)*(k-1) = 0 mod m^2-1, i.e., those with k-1 a multiple of m+1;
these will have order 1. Is this a surprise? Of course not: transposing
a square matrix in place requires mostly transpositions, except for the
elements on the diagonal, which remain fixed.

If m=2 and n=6, we need the order of 2 mod 2*6-1=11, which is 10.
Here the permutation has order 10, and so the length of each cycle must
divide 10. But in this case, the modulus 11 is prime, so for any
r<10, 2^r - 1 will be not only nonzero, but invertible, and hence
(2^r-1)*(k-1)=0 mod 11 means k=1 mod 11, i.e., k=1 or 12. So the
corners of the matrix stay fixed under transposition (of course) while
the other ten elements are all in one long cycle.

dave "Longer sigs for Rick Decker!" rusin