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