To my surprise, I was not able to find papers about this - probably searched the wrong keywords.

So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.

How do we reorder the array according to $f$ with memory and runtime as close to $O(1)$ and $O(n)$ as possible?

Are there any additional conditions when this task becomes easier? E.g. when we explicitly know a function $g$ is the inverse of $f$?

I know of an algorithm that follows cycles and traverses a cycle for each index to check if it's the least in its cycle, but again, it has worst-case $O(n^2)$ run time, though on average it seems to behave better...

  • An easy observation: If not only the array of the items but also the array containing the function f is writable, then it is easy to perform the task in O(n) time using O(1) integer registers (each of length O(log n) bits) and additional space for one item by just following each cycle. But this does not work if the function f is given on a read-only storage (or f is given only as an oracle), which I think is an assumption in this question. – Tsuyoshi Ito May 24 '11 at 18:38
  • 23
    Fich et al. 1995: $O(n \log n)$ time, $O(\log n)$ space. It also discusses some special cases. – Jukka Suomela May 24 '11 at 19:06
  • Yes, I am assuming we have f as an oracle. – jkff May 24 '11 at 21:33
  • 3
    @JukkaSuomela, you should make that into an answer. Also, considering that $f$ is an arbitrary permutation, a simple entropy argument yields $O( n \log n)$ space and/or time, so I would be surprised if you could do better than $O(n \log n)$ in time and space. – user834 Apr 23 '12 at 16:02

Option 0: Permuting In Place (1995) by Faith E. Fich , J. Ian Munro , Patricio V. Poblete $O(n \log n)$ time $O( \log^{2} n )$ space.

Option 1: Cheat by compressing your permutation to a succinct data structure, see Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Option 2: Use a prime cycle decomposition to store the perm succinctly and use that extra space to cheat http://oeis.org/A186202

Option 3: Keep track of the largest index of each cycle manipulated. For each iteration use the largest unseen index to move everything in its cycle by one. If it hits a seen index undo all that work because the cycle has already been manipulated. $O(n^2)$ time, $O(\#\text{cycles} * \log n)$ space.

Option 4: Keep track of the largest index of each cycle manipulated, but only do them in batches of distinct cycle lengths. For each iteration use the largest unseen index to move everything in it's cycle by one. If it hits a seen index undo all that work because thae cycle has already been manipulated. $O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$ time, $O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$ space.

Option 5: From same paper by Munro as Option 0, For $i = 1 .. n$ rotate the cycle of $p(i)$ if $i$ is the largest index in that cycle. $O(n^2)$ time and $O(\log n)$ space.

  • the compression methods may not save space in general: the worst case space to store a permutation is $n\log n$. 3, 4, and 5 seem in general as bad as either the solution OP already knows, or the solution by Fich, Munro, and Poblete. And that solution was already pointed out by @Jukka – Sasho Nikolov Jan 21 '14 at 23:01
  • #5 uses less space than #0 by a log (n) factor. – Chad Brewbaker Jan 21 '14 at 23:04

If you use the cycle representation of the permutation, you need 1 additional array element to store the item currently being permuted and you can run through the cycles in at worse O(N) operations.

  • 2
    jkff already said he knows the cycle-following algorithm, so he clearly wants the permutation itself to be treated as (close to) a black box. As he points out in the question, converting from a (nearly) black box to cycle representation could take O(n^2) time. – Joshua Grochow Jul 25 '13 at 20:15
  • Black box p(i) is fine. You just go around the cycle until you get back to i. The problem is one of Kolomogorov complexity to store the list of items that have been updated so you don't cycle them multiple times. Munro has bounds on that. itu.dk/people/ssrao/icalp03-a.pdf – Chad Brewbaker Jan 21 '14 at 17:51

Any permutation of N items can be converted to any other permutation using N-1 or fewer exchanges. Worst case for this method can require O(n^2) calls to the your oracle, F(). Start from the least position. Let x be the position we are currently swapping.

If F(x) >= x then swap positions x and F(x). Else, we must find where the item that was in position F(x) is currently in the list. We can do this with the following iteration. Let y=F(x). Do until y>=x: y=F(y): End Do. Now exchange positions x and y.

  • 3
    OP already said he knows how to do it in $O(n^2)$ time. – Jukka Suomela May 25 '11 at 9:25
  • Sorry. I am new to this group. I like this method because of its simplicity. I sometimes find simplicity faster than efficiency. I know another method that requires O(n) steps, but O(nlogn) space. – Russell Easterly May 26 '11 at 2:21
  • 1
    Russell, even allocating and zeroing O(n log n) space is already O(n log n), did you mean in the other direction? – jkff May 26 '11 at 3:12
  • You don't really have allocate and zero space. The basic idea is when F(x) > x we need to remember where we put the item at position x. For really large n, I would use a database and just keep a record of where item x gets moved. The record could be deleted when x gets to its final location. – Russell Easterly May 26 '11 at 3:27
  • 1
    But why are you then saying that it requires O(n log n) space? – jkff May 26 '11 at 4:02

This method uses the inverse of F and requires n bits of storage. If x is the position of an item in the original array, let G(x) be the position of the item in the sorted array. Let B be an n bit array. Set all n bits of B to 0.

FOR x=1 to n-1: IF B(x)==0 THEN: y=G(x): DO UNTIL x==y: Swap positions x and y: B(y)=1: y=G(y): LOOP: ENDIF: NEXT X

This method keeps swapping the item currently in position x to item's final position. The inner loop ends when the correct item gets swapped into position x. Since each swap moves at least one item to the item's final position, the inner Do loop can't excute more than n-1 times during the run. I think this method is O(n) time and space.

  • 2
    Have you looked at the paper? The two algorithms you list here are the two "obvious" ones. The paper has less obvious ones with different time-space tradeoffs, in particular much less space. – Yuval Filmus May 26 '11 at 18:06

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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