From: "Martin Vladic"
Newsgroups: sci.math
Subject: Problem with permutation cycles
Date: Wed, 8 Oct 1997 18:58:42 +0200
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?)
==============================================================================
From: rusin@teton.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Problem with permutation cycles
Date: 11 Oct 1997 17:44:06 GMT
In article <61ge4d$t6r@argos.tel.hr>,
Martin Vladic 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
==============================================================================
Date: Tue, 01 Dec 1998 13:35:17 -0800
From: "John A. Crow"
To: Dave Rusin
Subject: Re: looking for a bit of info
[deletia -- djr]
Thanks for the help. An article in the ACM TOMS [3 (1977) 104-110] had
a nice collection of results known about this problem. They note that
the longest cycle length is the one you present in your note. By unique
cycles I meant I was interested in how to find x and y so that their
associated cycles, C(x) and C(y) were different. Certainly you can
simply
choose y to be an element not in C(x), but I see now there is a better
way of doing this.
Again, thank you for your guidance and your note.
- John
______________________________________________________________________
John A. Crow crow@mnresearch.com
==============================================================================
55 #13866 68A10
Cate, Esko G.; Twigg, David W.
Algorithm $513.$ Analysis in in-situ transposition.
ACM Trans. Math. Software 3 (1977), no. 1, 104--110.
Let $A$ be an $m\times n$ array which is stored by columns; that is,
$A(I,J)=y\sb k$ where $k=m(J-1)+(I-1)$. If we let $p=n(I-1)+(J-1)$,
then $y\sb p=A(J,I)$ and the mapping $\pi(k)=p$ defines the
transposition permutation since the pairs $(y\sb k,y\sb p)$ are being
interchanged. The symmetry condition $\text{mod}(mn-1)$ given by
$\pi(-k)=-\pi(k)$ for $0\leq k\leq mn-2$ together with the fact that
the fixed points $\pi(k\sb i)=k\sb i$ form an arithmetic progression,
$k\sb i=id$ where $d=(mn-1)/\text{g.c.d.}\,[m-1,n-1]$ are properties
of the permutation which are exploited to provide revised versions of
previous algorithms: algorithm 302 [J. Boothroyd, Comm. ACM 10 (1967),
292--293] and algorithm 380 [S. Laflin and M. A. Brebner, Comm. ACM 13
(1970), 324--326]. In a series of test runs the revised 302 increased
efficiency by about $25%$ and the revised 380 gave improvements in the
range $20%$-7$0%$ with an average of $35%$. A FORTRAN listing is given
for revised 380 and a pair of tables summarizing the test runs is
shown.
Reviewed by Ralph A. Willoughby
© Copyright American Mathematical Society 1978, 1998