Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This problem originates from a programming interview problem. In that problem, we are asked to convert the array $[a_0, a_1, \cdots, a_{N-1}, b_0, b_1, \cdots, b_{N-1}, c_0, c_1, \cdots, c_{N-1}]$ into $[a_0, b_0, c_0, \cdots, a_{N-1}, b_{N-1}, c_{N-1}]$ in place. We can verify that the number originally at index $i$ would be moved to the new index $$ f(i) = 3(i \mod N)+[i/N], \qquad 0\leq i \leq 3N-1. $$ It also seems that if we repeatedly apply $f$ to the same index $i$, eventually there will be an integer $n$ such that $f^n(i)=i$.

My idea was that we repeatedly move the element at index $i$ to the index $f(i)$, and the element at the index $f(i)$ to the index $f^2(i)$ etc. Since these indices form a loop, eventually we'll move all the elements in the set $f^k(i)$ to their correct final positions.

When I program this idea, however, I need to find out the next element that has not been moved into its correct final position. For example, in the case N=1001, the next elements (x), the cyclic length, and the sum of the elements in the set $f^k(x)$ are the following:

x= 0, len= 1, sum= 0
x= 1, len= 234, sum= 351234
x= 2, len= 234, sum= 351234
x= 4, len= 234, sum= 351234
x= 5, len= 234, sum= 351234
x= 7, len= 234, sum= 351234
x= 10, len= 234, sum= 351234
x= 11, len= 234, sum= 351234
x= 14, len= 234, sum= 351234
x= 19, len= 78, sum= 117078
x= 20, len= 234, sum= 351234
x= 22, len= 234, sum= 351234
x= 35, len= 234, sum= 351234
x= 38, len= 78, sum= 117078
x= 61, len= 234, sum= 351234
x= 79, len= 18, sum= 27018
x= 158, len= 18, sum= 27018
x= 1501, len= 1, sum= 1501
x= 3002, len= 1, sum= 3002

What I'm interested to know, is for any positive interger $N$, to find a way to get the next "x" in the sequence in $O(1)$ time and $O(1)$ space. Thanks!

share|improve this question
3  
The following article considers the more general case of permuting a rectangular array in place. Your problem is the special case of this where the matrix has three rows. From this I suspect that there is no known answer to your question, only very good approximations. Fred G. Gustavson, Tadeusz Swirszcz, In-Place Transposition of Rectangular Matrices, Applied Parallel Computing. State of the Art in Scientific Computing. Lecture Notes in Computer Science, 2007, Springer Berlin / Heidelberg, full text available at springerlink.com/content/9755264224612x75 –  Zsbán Ambrus Mar 9 '12 at 20:24
    
Could you add the [algorithms] tag? –  Zsbán Ambrus Mar 9 '12 at 21:07
    
That paper seems very relevant. Thank you very much. –  Chong Luo Mar 9 '12 at 21:28
    
This is not efficient at all, but why don't you cyclically rotate the last $3N-1$ elements of the sequence until $b_0$ comes into place, then rotate the last $3N-2$ elements until $c_0$ comes into place, and so on. Since the cyclic order of the remaining elements is never disturbed, you always know exactly where things are... –  François G. Dorais Mar 10 '12 at 1:30
1  
Does this question have mathematical research interest? Would it fit better on a programming website? –  Gerry Myerson Mar 10 '12 at 4:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.