In-place array reordering?

Solution 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

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

Solution 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;
}

Solution 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);
   }
}

Solution 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));
  }
}