1
$\begingroup$

I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/

The matrix can be thought of as a permutation and its transposition as another permutation. I need to convert the first one into another. I have found a relation between the Cycles in the Permutation and the number of swaps required as:

Minimum Swaps = Total Elements in Permutation - Number of Cycles

However, I don't know how to calculate the matrix of size $2^a 2^b$ where $a+b \leq 500000$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The point of the problem is for you to solve it by yourself. You're not going to learn anything if someone solves it for you. $\endgroup$ – Yuval Filmus Jun 25 '13 at 4:06
  • $\begingroup$ I am not asking for a complete answer. I just want to learn on how it can be done. I am just asking for ideas. Nothing more. $\endgroup$ – divanshu Jun 25 '13 at 22:08
3
$\begingroup$

Let's take a simple example: $$ \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}' = \begin{pmatrix} a & d & g \\ b & e & h \\ c & f & i \end{pmatrix}.$$ So we need to exchange $(b,d),(f,h),(c,g)$, i.e. the answer is 3. Now try to generalize this to $A \times B$ matrices. Obtain a formula, substitute $A = 2^a$ and $B = 2^b$, and find a way to efficiently compute the result modulo a small prime $p$.

When $A = 2^a$ and $B = 2^b$, things look nicer. The permutation taking a position in the original matrix to the corresponding position in the transposed matrix corresponds to left shift by an amount $a$. Suppose $g = \mathrm{gcd}(a,b)$ and $a' = a/g,b' = b/g$. We can now think of the operation as a left shift by the amount $a'$ of a string of length $a'+b'$ over an alphabet of size $G = 2^g$. The number of orbits is then the number of necklaces of length $a'+b'$, which has an explicit formula. (The shift amount doesn't matter since $a'$ is invertible modulo $a' + b'$ due to $(a',b')=1$.)

Improve this answer
$\endgroup$
8
  • $\begingroup$ I had identified this way earlier. And this is not related to my question. My question is how to find the number of Permutation cycles in a matrix transposition. $\endgroup$ – divanshu Jun 25 '13 at 22:09
  • $\begingroup$ How far did you get in my algorithm? Did you find a formula for arbitrary $A,B$? When $A = B$, at least, it's not that difficult. You can start with that case. $\endgroup$ – Yuval Filmus Jun 26 '13 at 2:30
  • $\begingroup$ I am relying on the formula that such a matrix can be represented as: (a,b,c,d,e,f,g,h,i) and transposition as: (a,d,g,b,e,h,c,f,i). Then transposition as a product of disjoint cycles will be: (a)(b,d)(c,g)(e)(f,h)(i). Now answer would be: Total elements - Cycles or (9-6) which is same as your answer 3. For, A=B=N, answer would be simply, ((N)*(N-1))/2. Even for ranges where total elements in matrix are within order of 10^6 can be found using cycles. But, the thing is A and B are raised to 2, which increases the permutation length to be exponential. This is causing problems for me. $\endgroup$ – divanshu Jun 26 '13 at 13:35
  • 1
    $\begingroup$ Ok. So suppose $N = 2^n$. How can you compute $N(N-1)/2 \pmod{p}$ efficiently? Hint: You never need to actually compute $N$. $\endgroup$ – Yuval Filmus Jun 26 '13 at 16:05
  • 1
    $\begingroup$ I recommend you take some small cases (not necessarily powers of $2$), compute the result, and try to generalize. There is probably a simple formula in the case $A \neq B$ as well. Don't expect me to solve your problem for you. $\endgroup$ – Yuval Filmus Jun 26 '13 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.