In-place array reordering?

Question

Let's say I have an array a of length n and a second array indices, also of length n. indices contains some arbitrary permutation of the sequence [0, n). I want to to rearrange a such that it's in the order specified by indices. For example, using D syntax:

auto a = [8, 6, 7, 5, 3, 0, 9];
auto indices = [3, 6, 2, 4, 0, 1, 5];
reindexInPlace(a, indices);
assert(a == [5, 9, 7, 3, 8, 6, 0]);

Can this be done in both O(1) space and O(n) time, preferably without mutating indices?

Waller

By virtue of it having have up to 2*n elements, isn't it already in O(n) space? So you don't increase space complexity by utilizing a third array to simplify things. – Browne

@glowcoder: here O(1) obviously means that only constant additional space is allowed. Equivalently, the algorithm should be in place. – Ubiquitous

If anyone found the solution with O(n) time O(1) space and without mutating the indices, please share or if you have proved it is impossible, please share the proof. – Waksman

Answer 1

With mutating indices :(. Without looks hard (see stable in-place mergesort).

a = [8, 6, 7, 5, 3, 0, 9]
indices = [3, 6, 2, 4, 0, 1, 5]

for i in xrange(len(a)):
    x = a[i]
    j = i
    while True:
        k = indices[j]
        indices[j] = j
        if k == i:
            break
        a[j] = a[k]
        j = k
    a[j] = x

print a

Heterosis

I think this is also O(N^2) because in the inner loop the expected time to find the point where k == i is O(N) and you're doing O(N) of these loops. – Waller

@dsimcha: Incorrect. The inner cycle will never re-process alrady processed elements. For this reason it can't possibly be O(N^2). This algorithm makes at most two passes over each element, which makes it O(2N) = O(N). – Carthusian

The number of times the inner loop is "activated" (i.e it actually cycles, as opposed to breaking immediately) is equal to the number of cycles in the permutation. Each "activation" of inner loop makes as many iterations as there are nodes in the cycle. So, the total number of inner iterations is always exactly N, not N^2. This is why this algorithm is O(N). – Carthusian

Ok, my misunderstanding, then. +1. – Waller

+1 for actually solving the problem unlike the other answers that just conceal cheating moderately well. :-) – Smallminded

Answer 2

This is what I call a "permute from" algorithm. In C-like language it would look as follows

  for (i_dst_first = 0; i_dst_first < n; ++i_dst_first)
  {
    /* Check if this element needs to be permuted */

    i_src = indices[i_dst_first];
    assert(i_src < n);
    if (i_src == i_dst_first)
      /* This element is already in place */
      continue;

    i_dst = i_dst_first;
    pending = a[i_dst];

    /* Follow the permutation cycle */

    do
    {
      a[i_dst] = a[i_src];
      indices[i_dst] = i_dst;

      i_dst = i_src;
      i_src = indices[i_src];
      assert(i_src != i_dst);

    } while (i_src != i_dst_first);

    a[i_dst] = pending;
    indices[i_dst] = i_dst;
  }

Note though that this algorithm destroys the index array. I call it "permute from" since the index[i] value specifies from where to take the i-th element of the resultant sequence.

Note also, that the number of "element move" operations required for in-place permutation of a sequence is equal to number of misplaced elements + number of cycles in the permutation. This algorithm achieves this limit, so in terms of the number of moves no better algorithm is possible.

Potential problem with this algorithm is that it is based on "juggling" approach, making its cache behavior far from optimal. So, while this algorithm is the best one in theory, it could lose to some more "practical" algorithms in real life.

One can also implement a "permute to" algorithm, where index[i] value specifies where to relocate the original i-th element.

Carthusian

I don't see much point in it in most cases if it destroys the index array, unless you really don't need the index array afterwords. If it's gonna be O(N) memory anyhow, you may as well just copy a while rearranging it. – Waller

Well, this is specifically for situations when you don't need the index array afterwards. I don't understand your "memory" argument. Non-on-place version will require O(N) additional memory. This algorithm (assuming you can sacrifice the index contents) requires O(1) additional memory. – Carthusian

Right, but if you do need the index array afterwords, you just have to copy that instead. – Waller

@dsimcha: You are right. Again, if you ultimately need the result back in its original location (i.e. you really need the "in-place" behavior), then you'll have to copy that back to from the auxiliary array. – Carthusian

Note, that the reason we modify index is to mark the "already in place" elements. If you don't want to destroy index, you can re-implement this algorithm with an extra boolean array (which can be implemented as bit-array), which is used to mark already processed elements instead of index. In this case you can keep index unchanged. – Carthusian

+1 for actually solving the problem (to the degree it's possible) – Smallminded

you lack a last indices[i_dst] = i_dst; after a[i_dst] = pending; -- otherwise you just go into an infinite loop – Harvestman

typos can happen, I'm surprised the answer lived a whole year without anyone noticing it's flawed :) – Harvestman

@Gregory Pakosz: Yes, you are right. Thanks for pointing it out. I "converted" the above from my local working version (different interface, different variable names etc.), which has that last assignment in place. Apparently I accidentally removed it during the "conversion". – Carthusian

@AndreyT: Do you know how to implement "permute to"? Is it more complicated than "permute from"? (My version for "permute from" is pretty simple, but I can't figure out how to make the reverse work: for (size_t i = 0; i != n; ++i) for (size_t j = i; ; ) { swap(j, indices[j]); if (j == i) { break; } swap(items[j], items[indices[j]]); }) – Exonerate

This is exactly the same algorithm as QWERTY's answer, but this version is much easier to understand. – Forensic

Answer 3

If a is an array of integers, then an O(n)-time, O(1)-space algorithm is possible that keeps the order of permutation indices. In this case we can permute a into indexes and use a as a temporary storage of the inverse permutation. After the permutation is performed, the arrays a and indices are swapped, and indices is inverted in situ using e.g. algorithm J from TAoCP. The following is a working Java program:

int [] a = {8, 6, 7, 5, 3, 0, 9};
int [] indices = {3, 6, 2, 4, 0, 1, 5};
int n = indices.length;
int i, j, m;    
// permute a and store in indices
// store inverse permutation in a
 for (j = 0; j < n; ++j) {
     i = indices[j]; indices[j] = a[i]; a[i] = j;
 }
 // swap a and indices
 for (j = 0; j < n; ++j) {
     i = indices[j]; indices[j] = a[j]; a[j] = i;
 }
 // inverse indices permutation to get the original
 for (i = 0; i < n; ++i) {indices[i] = -indices[i] - 1;}
 for (m = n - 1; m >= 0; --m) {
     // for (i = m, j = indices[m]; j >= 0; i = j, j = indices[j]) ;
     i = m; j = indices[m]; 
     while (j >= 0) {i = j; j = indices[j];}
     indices[i] = indices[-j - 1];
     indices[-j - 1] = m;
}

Ubiquitous

+1. Very interesting and does technically answer the question I asked. However, I'm a little disappointed that it won't work if a is an array of some type other than integers. – Waller

This is not in-place: indices[i] = -indices[i] - 1; It assumes at least one unused bit is available in each element of indices, i.e. it uses O(n) additional space. – Smallminded

@R.: The algorithm J, which I refer above and which I use, is called "inverse of a permutation in place". This name is justified and accepted by the community. Our (abstract) machine operates on integers that can be negative. The indices are nonnegative integers stored in the data type integer, and hence can be negated. – Ubiquitous

My abstract machine isn't a JVM and thus has unsigned integers. :-) – Smallminded

Answer 4

This answers the question when indices array is mutable.

Here is a solution when it is not mutable.

void mutate(int[] input, int[] indices) {
   int srcInd;

   for (int tarInd = 0; tarInd < input.length; tarInd++) {
      srcInd = indices[tarInd];
      while(srcInd < tarInd) {

         // when src is behind, it will have it's final value already and the original
         // value would have been swapped with src's src pos. Keep searching for the
         // original value until it is somewhere ahead of tarInd.
         srcInd = indices[srcInd];
      }
      swap(input, srcInd, tarInd);
   }
}

Viscous

Answer 5

I think the classic way to deal with this problem is to work round the cycles, and to do this you need a marker bit per data item from somewhere. Here I pinched the top bit of the index array, which you could restore - of course this assumes that you don't have -ve array indexes or are using all bits of an unsigned number as an index. One reference for this is Knuth Volume 1 section 1.3.3 answer to question 12, which deals with the special case of transposing a matrix. Knuth gives references to slower in-place methods. The paper "Permuting in Place" by Fich, Munro, and Poblete claims nlogn time and O(1) space in the worst case.

import java.util.Arrays;

public class ApplyPerm
{
  public static void reindexInPlace(int[] rearrangeThis, int[] indices) 
  {
    final int TOP_BIT = 0x80000000;
    for (int pos = 0; pos < rearrangeThis.length; pos++)
    {
      if ((indices[pos] & TOP_BIT) != 0)
      { // already dealt with this
        continue;
      }
      if (indices[pos] == pos)
      { // already in place
        continue;
      }
      // Now shift an entire cycle along
      int firstValue = rearrangeThis[pos];
      int currentLocation = pos;
      for (;;)
      {
        // pick up untouched value from here
        int replaceBy = indices[currentLocation];
        // mark as dealt with for the next time we see it
        indices[currentLocation] |= TOP_BIT;
        if (replaceBy == pos)
        { // have worked our way round
          rearrangeThis[currentLocation] = firstValue;
          break;
        }
        if ((replaceBy & TOP_BIT) != 0)
        {
          throw new IllegalArgumentException("Duff permutation");
        }
        // Move value up 
        rearrangeThis[currentLocation] = rearrangeThis[replaceBy];
        // and fill in source of value you have just moved over
        currentLocation = replaceBy;
      }
    }
  }
  public static void main(String[] s)
  {
    int[] a = new int[] {8, 6, 7, 5, 3, 0, 9};
    int[] indices = new int[] {3, 6, 2, 4, 0, 1, 5};
    reindexInPlace(a, indices);
    System.out.println("Result is " + Arrays.toString(a));
  }
}

Optician

Answer 6

You can do this by hiding the values in the real array. By this way you can do this in both O(1) space and O(n) time.

Basically, you traverse through your indices array first, store the value of the indice array in the correct position. Now this can be done in the algorithm of your choice. For me, I would simply store the number's trailing bits from the Most Significant bit position. Do this in one traversal. Now the base array would be messed up.

During the second traversal store all the upper half bits to lower half.

The obvious disadvantage of this technique is that the stored integer value can hold as much as half the bits. Meaning if you are dealing with 4 byte integer, the values can only be of 2 bytes. However instead of using up half the array as show in the code below, it can be enhanced by using a better algorithm where you hide the value in the index array. Here you will require the max bits reserved in worst case would be the length of the array rather than constant 16 in the previous case. It will perform worst than the former when the length exceeds 2 power 16.

import java.util.Arrays;
class MyClass {
    public static void main(String[] args) {
        MyClass myClass = new MyClass();
        int[] orig_array = {8, 6, 7, 5, 3, 0, 9};
        int[] indices = {3, 6, 2, 4, 0, 1, 5};
        myClass.meth(orig_array, indices);
    }

    public void meth(int[] orig_array, int[] indices){
        for(int i=0;i<orig_array.length;i++)
            orig_array[i] += orig_array[indices[i]] + orig_array[indices[i]] << 15 ;
        for(int i=0;i<orig_array.length;i++)
            orig_array[i] = orig_array[i] >> 16;
        System.out.print(Arrays.toString(orig_array));
    }
}

Metcalf

I would say that this approach is O(n) space. There is nothing like half words in the complexity theory. – Ubiquitous

@Jiri : if you can tweak your algorithm, for instance, instead of hiding that value in the orignial array, you can hide in the index array. This would not be half as bad but will require only the length of the array in the worst case. – Metcalf

Answer 7

Here's a C++ version (it modifies the indices):

#include <algorithm>
#include <iterator>

template<class It, class ItIndices>
void permutate_from(
    It const begin,
    typename std::iterator_traits<It>::difference_type n,
    ItIndices indices)
{
    using std::swap;
    using std::iter_swap;
    for (typename std::iterator_traits<It>::difference_type i = 0; i != n; ++i)
    {
        for (typename std::iterator_traits<ItIndices>::value_type j = i; ; )
        {
            swap(j, indices[j]);
            if (j == i) { break; }
            iter_swap(begin + j, begin + indices[j]);
        }
    }
}

Example:

int main()
{
    int items[]     = { 2, 0, 1, 3 };
    int indices[]   = { 1, 2, 0, 3 };
    permutate_from(items, 4, indices);
    // Now items[] == { 0, 1, 2, 3 }
}

Exonerate

Answer 8

JavaScript version

var input = [1,2,3,4,5],
    specArr = [0,2,1,4,3];

function mutate(input, specArr) {

    var visited = [0,2]
    for(var i=0; i<specArr.length; i++) {
        var tmp;

        //keep track of array items we've already looped through (wouldn't want to mutate twice :D)
        visited.push(specArr[i]);
        // if index hasn't changed we do nothing to input arr
        if (visited.indexOf(1) < 0) {
          // if it has changed temporarily store the value
          tmp = input[i];
          //swap input array item with spec item
          input[i] = input[specArr[i]];
          //swap specced array item with input item above
          input[specArr[i]] = tmp;
        }
    }
}

mutate(input, specArr);    

Punctuation