33
$\begingroup$

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...

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Commented May 24, 2011 at 18:38
  • 25
    $\begingroup$ Fich et al. 1995: $O(n \log n)$ time, $O(\log n)$ space. It also discusses some special cases. $\endgroup$ Commented May 24, 2011 at 19:06
  • $\begingroup$ Yes, I am assuming we have f as an oracle. $\endgroup$
    – jkff
    Commented May 24, 2011 at 21:33
  • 3
    $\begingroup$ @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. $\endgroup$
    – user834
    Commented Apr 23, 2012 at 16:02

5 Answers 5

5
$\begingroup$

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 Succinct representation of permutations.

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Commented Jan 21, 2014 at 23:01
  • $\begingroup$ #5 uses less space than #0 by a log (n) factor. $\endgroup$ Commented Jan 21, 2014 at 23:04
1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 25, 2013 at 20:15
  • $\begingroup$ 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 $\endgroup$ Commented Jan 21, 2014 at 17:51
0
$\begingroup$

First off, I came up with the same algorithm as mentioned by Russell Easterly but I have an additional tweak.

This is the initial algorithm:

for each increasing index i from 1 to length of array

movealong the permutation cycle of the current elementstarting at$f(i)$ and

stop at the first permutation entry$k = f(j)$where$j \le i < k$

or else$k = NaN$

swap array element at i with element at kif k is not NaN

This alone has a worst-case which is only twice as fast as the algorithm in the OP. But the common average case is much faster. For infinitely large N – under consideration of the geometric distribution of randomly generated permutation functions with $p = P(f(j) > i) = 0.5$ for all $j,i$, we would get N times the expectancy value which is $\mathcal{O}(N)$ time complexity with $\mathcal{O}(1)$ space complexity but it might be worse for real data with finite arrays where the parameter of the geometric distribution is a random process. It is certainly a faster and easier algorithm to implement than the one in the original post.

Now we can optimize the worst case by introducing an opposite function which goes into opposite direction, with decreasing index from last to first and searching for a $f(j \ge i) < i$ each time.

Count the number of permutation lookups of both functions without swapping. Then choose the function with less required lookups to do the job with swapping. You can count in parallel or interleaved (assume a fair share of time so that the slower function does not get most of the time) and interrupt the counting of the slower function when it exceeds the returned count of the faster one. This case, we avoid degenerate cases and probably get a solid average case complexity as worst case (I conjecture). If this is true it would only take 3 times the average complexity of the initial algorithm which is better than square complexity in time and is guaranteed to have constant space complexity since no copies are created and swaps are inplace.

Option 2

I found an inplace-algorithm with assumed (measured) worst case $\mathcal{O}(N·log2(N))$. I thought about avoiding unnecessary visits of permutation entries and noticed that the relation between the index and its permutation entry and is already some kind of binary flag property. Python-Code:

def compute_permutation(array, pi):
    for i in range(len(array)):
        if (j := pi[i]) > i:
            array[i], array[j] = array[j], array[i]
    
    for i in range(len(array)-1,0, -1):
        if (j := pi[i]) < i:
            while pi[j] > j or j > i:
                j = pi[j]
            array[i], array[j] = array[j], array[i]

The algorithm yet allows for some further optimizations like avoiding walking through the full cycle for the first permutation entry which points back. I wonder, if walking through the cycles a logarithmic number of times is actually necessary when there are only few array elements left at position < i.

Option 3

For a special case with mutable permutation, if destroying the permutation is not minded, then you can do this (Python):

def compute_permutation(array, pi):
    for i in range(len(array)):
        j = i
        while i != (k := pi[i]):
            array[j], array[k] = array[k], array[j]
            pi[i], pi[k] = pi[k], pi[i]
            j = k

Does not allocate additional memory besides local variables and has $\mathcal{O}(N)$ time complexity and $\mathcal{O}(1)$ space complexity. The trick is to exploit the permutation as buffer which turns it into a linear range of indices at the end. This is probably not worse than the compression options found in the answer of Chad Brewbaker which also destroys the original value of the permutation entries.

Option 4

If there is a way to extract the original index from a given array-element in $\mathcal{O}(1)$ steps and space via a function index_of() then you can do even better without modifying the permutation function but same complexity lower bounds. Just use the comparison of that element index against the permutation entry as a flag:

def compute_permutation(array, pi):
    for i in range(len(array)):
        if array[i].index_of() != pi[i]:
            j = i
            while i != (k := pi[j]):
                array[j], array[k] = array[k], array[j]
                j = k

Option 5

If there is no way to extract the original index of a value in $\mathcal{O}(1)$ time then there is still a way that will always work in practice, even though some could consider it cheating. You can use signed indices and use the sign bit as a flag that is cleared at the end of the algorithm. Set the flag for permutation entries whose corresponding element was already swapped to the correct position. This is always feasible in practice, at least in Java which always reserves a sign bit for integer values even though it is useless for indices.

void compute_permutation(Object[] array, int[] pi)
{
    for(int i=0; i<array.length; i++)
    {
        if (pi[i] >= 0)
        {
            for(int j=i, k; i != (k = pi[j]); j = k)
            {
                Object tmp = array[j];
                array[j] = array[k];
                array[k] = tmp;
                pi[j] = ~pi[j];
            }
        }
    }

    for(int i=0; i<pi.length; i++) pi[i] = ~pi[i];
}

This allows for practical inplace solutions with $\mathcal{O}(N)$ overhead and no additional allocation. Only restriction: requires a writable permutation array.

Big disadvantage: any modification to the permutation entries is not thread-safe! Would require permutation copies for nested or concurrent calls with the same permutation.

Instead of modifying permutation entries, modifying the array elements with a flag would be more useful. Low-Level languages often have access to reference values (addresses) where an unused bit can be set as a flag and later removed. Non-negative integer values could use the sign as flag as well (in Java). Since the input array needs to be modified anyways with an inplace algorithm, it would not cause additional problems.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ OP already said he knows how to do it in $O(n^2)$ time. $\endgroup$ Commented May 25, 2011 at 9:25
  • $\begingroup$ 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. $\endgroup$ Commented May 26, 2011 at 2:21
  • 1
    $\begingroup$ Russell, even allocating and zeroing O(n log n) space is already O(n log n), did you mean in the other direction? $\endgroup$
    – jkff
    Commented May 26, 2011 at 3:12
  • $\begingroup$ 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. $\endgroup$ Commented May 26, 2011 at 3:27
  • 1
    $\begingroup$ But why are you then saying that it requires O(n log n) space? $\endgroup$
    – jkff
    Commented May 26, 2011 at 4:02
-2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Commented May 26, 2011 at 18:06

Your Answer

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

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