1
$\begingroup$

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!

$\endgroup$
9
  • 3
    $\begingroup$ 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 $\endgroup$ Mar 9, 2012 at 20:24
  • $\begingroup$ Could you add the [algorithms] tag? $\endgroup$ Mar 9, 2012 at 21:07
  • $\begingroup$ That paper seems very relevant. Thank you very much. $\endgroup$
    – Chong Luo
    Mar 9, 2012 at 21:28
  • $\begingroup$ 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... $\endgroup$ Mar 10, 2012 at 1:30
  • 1
    $\begingroup$ Does this question have mathematical research interest? Would it fit better on a programming website? $\endgroup$ Mar 10, 2012 at 4:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.