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