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?

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

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.

Answer 3

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

Answer 4

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

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

Answer 6

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

Answer 7

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

Answer 8

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