How to rearrange an array by indices array?

Question

Given an array arr and an array of indices ind, I'd like to rearrange arr in-place to satisfy the given indices. For example:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

rearrange(arr, ind);

console.log(arr); // => ["B", "E", "D", "F", "A", "C"]

Here is a possible solution that uses O(n) time and O(1) space, but mutates ind:

function swap(arr, i, k) {
  var temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
}

function rearrange(arr, ind) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (ind[i] !== i) {
      swap(arr, i, ind[i]);
      swap(ind, i, ind[i]);
    }
  }
}

What would be the optimal solution if we are limited to O(1) space and mutating ind is not allowed?

---

Edit: The algorithm above is wrong. See this question.

Answer 1

This is the "sign bit" solution.

Given that this is a JavaScript question and the numerical literals specified in the ind array are therefore stored as signed floats, there is a sign bit available in the space used by the input.

This algorithm cycles through the elements according to the ind array and shifts the elements into place until it arrives back to the first element of that cycle. It then finds the next cycle and repeats the same mechanism.

The ind array is modified during execution, but will be restored to its original at the completion of the algorithm. In one of the comments you mentioned that this is acceptable.

The ind array consists of signed floats, even though they are all non-negative (integers). The sign-bit is used as an indicator for whether the value was already processed or not. In general, this could be considered extra storage (n bits, i.e. O(n)), but as the storage is already taken by the input, it is not additional acquired space. The sign bits of the ind values which represent the left-most member of a cycle are not altered.

Edit: I replaced the use of the ~ operator, as it does not produce the desired results for numbers equal or greater than 2³¹, while JavaScript should support numbers to be used as array indices up to at least 2³² - 1. So instead I now use k = -k-1, which is the same, but works for the whole range of floats that is safe for use as integers. Note that as alternative one could use a bit of the float's fractional part (+/- 0.5).

Here is the code:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

rearrange(arr, ind);

console.log('arr: ' + arr);
console.log('ind: ' + ind);

function rearrange(arr, ind) {
    var i, j, buf, temp;
    
    for (j = 0; j < ind.length; j++) {
        if (ind[j] >= 0) { // Found a cycle to resolve
            i = ind[j];
            buf = arr[j];
            while (i !== j) { // Not yet back at start of cycle
                // Swap buffer with element content
                temp = buf;
                buf = arr[i];
                arr[i] = temp;
                // Invert bits, making it negative, to mark as visited
                ind[i] = -ind[i]-1; 
                // Visit next element in cycle
                i = -ind[i]-1;
            }
            // dump buffer into final (=first) element of cycle
            arr[j] = buf;
        } else {
            ind[j] = -ind[j]-1; // restore
        }
    }
}

Although the algorithm has a nested loop, it still runs in O(n) time: the swap happens only once per element, and also the outer loop visits every element only once.

The variable declarations show that the memory usage is constant, but with the remark that the sign bits of the ind array elements -- in space already allocated by the input -- are used as well.

Answer 2

Index array defines a permutation. Each permutation consists of cycles. We could rearrange given array by following each cycle and replacing the array elements along the way.

The only problem here is to follow each cycle exactly once. One possible way to do this is to process the array elements in order and for each of them inspect the cycle going through this element. If such cycle touches at least one element with lesser index, elements along this cycle are already permuted. Otherwise we follow this cycle and reorder the elements.

function rearrange(values, indexes) {
    main_loop:
    for (var start = 0, len = indexes.length; start < len; start++) {
        var next = indexes[start];
        for (; next != start; next = indexes[next])
            if (next < start) continue main_loop;

        next = start;
        var tmp = values[start];
        do {
            next = indexes[next];
            tmp = [values[next], values[next] = tmp][0]; // swap
        } while (next != start);
    }
    return values;
}

This algorithm overwrites each element of given array exactly once, does not mutate the index array (even temporarily). Its worst-case complexity is O(n²). But for random permutations its expected complexity is O(n log n) (as noted in comments for related answer).

---

This algorithm could be optimized a little bit. Most obvious optimization is to use a short bitset to keep information about several indexes ahead of current position (whether they are already processed or not). Using a single 32-or-64-bit word to implement this bitset should not violate O(1) space requirement. Such optimization would give small but noticeable speed improvement. Though it does not change worst case and expected asymptotic complexities.

To optimize more, we could temporarily use the index array. If elements of this array have at least one spare bit, we could use it to maintain a bitset allowing us to keep track of all processed elements, which results in a simple linear-time algorithm. But I don't think this could be considered as O(1) space algorithm. So I would assume that index array has no spare bits.

Still the index array could give us some space (much larger then a single word) for look-ahead bitset. Because this array defines a permutation, it contains much less information than arbitrary array of the same size. Stirling approximation for ln(n!) gives n ln n bits of information while the array could store n log n bits. Difference between natural and binary logarithms gives us to about 30% of potential free space. Also we could extract up to 1/64 = 1.5% or 1/32 = 3% free space if size of the array is not exactly a power-of-two, or in other words, if high-order bit is only partially used. (And these 1.5% could be much more valuable than guaranteed 30%).

The idea is to compress all indexes to the left of current position (because they are never used by the algorithm), use part of free space between compressed data and current position to store a look-ahead bitset (to boost performance of the main algorithm), use other part of free space to boost performance of the compression algorithm itself (otherwise we'll need quadratic time for compression only), and finally uncompress all the indexes back to original form.

To compress the indexes we could use factorial number system: scan the array of indexes to find how many of them are less than current index, put the result to compressed stream, and use available free space to process several values at once.

The downside of this method is that most of free space is produced when algorithm comes to the array's end while this space is mostly needed when we are at the beginning. As a result, worst-case complexity is likely to be only slightly less than O(n²). This could also increase expected complexity if not this simple trick: use original algorithm (without compression) while it is cheap enough, then switch to the "compressed" variant.

If length of the array is not a power of 2 (and we have partially unused high-order bit) we could just ignore the fact that index array contains a permutation, and pack all indexes as if in base-n numeric system. This allows to greatly reduce worst-case asymptotic complexity as well as speed up the algorithm in "average case".

Answer 3

This proposal utilizes the answer of Evgeny Kluev.

I made an extension for faster processing, if all elements are already treated, but the index has not reached zero. This is done with an additional variable count, which counts down for every replaced element. This is used for leaving the main loop if all elements are at right position (count = 0).

This is helpful for rings, like in the first example with

["A", "B", "C", "D", "E", "F"]
[ 4,   0,   5,   2,   1,   3 ]

index 5: 3 -> 2 -> 5 -> 3
index 4: 1 -> 0 -> 4 -> 1

Both rings are at first two loops rearranged and while each ring has 3 elements, the count is now zero. This leads to a short circuit for the outer while loop.

function rearrange(values, indices) {
    var count = indices.length, index = count, next;

    main: while (count && index--) {
        next = index;
        do {
            next = indices[next];
            if (next > index) continue main;
        } while (next !== index)
        do {
            next = indices[next];
            count--;
            values[index] = [values[next], values[next] = values[index]][0];
        } while (next !== index)
    }
}

function go(values, indices) {
    rearrange(values, indices);
    console.log(values);
}

go(["A", "B", "C", "D", "E", "F"], [4, 0, 5, 2, 1, 3]);
go(["A", "B", "C", "D", "E", "F"], [1, 2, 0, 4, 5, 3]);
go(["A", "B", "C", "D", "E", "F"], [5, 0, 1, 2, 3, 4]);
go(["A", "B", "C", "D", "E", "F"], [0, 1, 3, 2, 4, 5]);

Answer 4

This answer has been updated to satisfy OP's conditions

In this answer there are no temp arrays and ind array doesn't get re-ordered or sorted by any means. All replacing operations are done in a single pass. getItemIndex function receives only a shallow portion of the ind array to work with. It's just done by harnessing all the information hidden in the ind array.

It's key to understand that the ind array keeps all history for us.

We have the following information by examining the ind array.

1. By looking at the items we find the index map of the corresponding item at arr array.
2. Each items index tells us how many swaps done before. We get history.
3. Each items index also tells if there was a previous swap related with the current index position where did the previous element go. We can do like ind.indexOf(i); Anyways here is the code;

I have added a few functions like Array.prototype.swap() to make the code interpreted easier. Here is the code.

Array.prototype.swap = function(i,j){
  [this[i],this[j]] = [this[j],this[i]];
  return this;
};

function getItemIndex(a,i){
  var f = a.indexOf(i);
  return f !=-1 ? getItemIndex(a,f) : i;
}

function sort(arr,ind){
  ind.forEach((n,i,x) => x.indexOf(i) > i ? arr.swap(i,x[i]) // item has not changed before so we can swap 
                                          : arr.swap(getItemIndex(ind.slice(0,i),i),x[i])); // item has gone to somwhere in previous swaps get it's index and swap
  return arr;
}

var arr = ["A", "B", "C", "D", "E", "F"],
    ind = [4, 0, 5, 2, 1, 3];


console.log(sort(arr,ind),ind);

Ok the very final version of this code is this. It is very simplified and includes a test case with 26 letters. Each time you run you will get a different purely random unique indexes map.

Array.prototype.swap = function(i,j){
  i !=j && ([this[i],this[j]] = [this[j],this[i]]);
  return this;
};

Array.prototype.shuffle = function(){
  var i = this.length,
      j;
  while (i > 1) {
    j = ~~(Math.random()*i--);
    [this[i],this[j]] = [this[j],this[i]];
  }
return this;
};

var   arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"],
      ind = (new Array(arr.length)).fill("").map((e,i) => e = i).shuffle();
console.log(JSON.stringify(arr));
console.log(JSON.stringify(ind));

function getItemIndex(a,i,j){
  var f = a.indexOf(i);
  return f < j ? getItemIndex(a,f,j) : i;
}

function sort(arr,ind){
  ind.forEach((n,i,x) => arr.swap(getItemIndex(ind,i,i),n));
  return arr;
}
console.log(JSON.stringify(sort(arr,ind)));
console.log(JSON.stringify(ind));

So ok as per the comment from Trincot here it goes with an iterative getItemIndex() function.

Array.prototype.swap = function(i,j){
  i !=j && ([this[i],this[j]] = [this[j],this[i]]);
  return this;
};

Array.prototype.shuffle = function(){
  var i = this.length,
      j;
  while (i > 1) {
    j = ~~(Math.random()*i--);
    [this[i],this[j]] = [this[j],this[i]];
  }
return this;
};

var   arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"],
      ind = (new Array(arr.length)).fill("").map((e,i) => e = i).shuffle();
console.log(JSON.stringify(arr));
console.log(JSON.stringify(ind));

function getItemIndex(a,i){
  var f = a.indexOf(i),
      j;
  if (f >= i) return i; // this element hasn't been moved before.
  while (f < i) {       // this element has been swapped so get this elements current index
   j = f;
   f = a.indexOf(f);
  }
  return j;
}

function sort(arr,ind){
  ind.forEach((n,i,x) => arr.swap(getItemIndex(ind,i),n));
  return arr;
}
console.log(JSON.stringify(sort(arr,ind)));
console.log(JSON.stringify(ind));

Answer 5

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

function rearrange(arr, ind){
  var map = [];
  for (var i = 0; i < arr.length; i++)   map[ind[i]] = arr[i];
  for (var i = 0; i < arr.length; i++)   arr[i] = map[i];
}

rearrange(arr, ind);

console.log(arr);

That works but, because I'm not a smart developper, I assume it's probably not the fastest algorithm.

Answer 6

Below, one may find a PARTIAL solution for a case when we have only ONE cycle, i.e.

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 2, 5, 0, 1, 3];

function rearrange( i, arr, ind, temp ){
    if( temp ){
        if( arr[ind[i]] ){
            var temp2 = arr[ind[i]];
            arr[ind[i]] = temp;
            rearrange( ind[i], arr, ind, temp2 );
        }
        else{                                           // cycle
            arr[ind[i]] = temp;
            // var unvisited_index = ...;
            // if( unvisited_index ) rearrange( unvisited_index, arr, ind, "" );
        }
    }
    else{
        if( i == ind[i] ){
            if( i < arr.length ) rearrange( i + 1, arr, ind, temp );    
        }
        else{
            temp = arr[ind[i]];
            arr[ind[i]]=arr[i];
            arr[i] = "";
            i = ind[i];
            rearrange(i, arr, ind, temp );
        }
    }
}

rearrange( 0, arr, ind, "" );

To make this solution to work for a general case, we need to find total numbers of unique cycles and one index from each of them.

For the OP example:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

There are 2 unique cycles:

4 -> 1 -> 0 -> 4
5 -> 3 -> 2 -> 5

If one runs

rearrange( 0, arr, ind, "" );
rearrange( 5, arr, ind, "" );

S(he) will get desirable output for the OP problem.

Answer 7

I'm not sure on the time, but the map function does appear to do what was requested. It's an option, but since I don't know the inner workings of .map then I can't say for sure this is what you're looking for.

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

arr = ind.map(function(value)
{ return arr[value]; });

Another solution that doesn't use the map function could look something like this:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

var temp = [];

for (var i = 0, ind_length = ind.length; i < ind_length; i++) 
{ 
    var set_index = ind[i];
    temp.push(arr[set_index]); 
    delete arr[set_index]; 
}

arr = temp;

This makes good use of space by using the delete option which also keeps the indexes from shifting. Since it's only doing one loop I imagine the execution is rather fast. Since the commands are very basic and simple this should be a viable solution. It's not quite what was asked which was a swap with no extra space used, but it comes pretty close. I'm new to answering questions like this one so please... constructive criticism.

Answer 8

Try this:

var result = new Array(5);
for (int i = 0; i < result.length; i++) {
    result[i] = arr[ind[i]];
}
console.log(arr);

Answer 9

I am using ind as indexes in it's own order

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
var obj = {}
for(var i=0;i<arr.length;i++)
    obj[ind[i]]=arr[i];
console.log(obj);

Working Fiddle