Is it possible to rearrange an array with constant memory overhead?

Question

I stumbled upon this while reading some StackOverflow questions but could not find a satisfying answer.

Suppose we have an array A of length n containing its indexes from 0 to n-1 in a random fashion. Is it possible to rearrange the array so that its outcome is A[ A[i] ] with constant O(1) memory overhead?

Example:

A = [ 3, 2, 0, 1 ]
rearrange( A )
A = [ 1, 0, 3, 2 ]

If it is possible an outline of the algorithm would be nice. Otherwise an explanation why it is not possible. Since inplace sorting is a thing maybe this works similar.

Clarification: If you do not have the memory constraint the algorithm is trivial:

A = [ 3, 2, 0, 1 ]
A_r = Array_of_size( A )
for i = 0 to Arraysize - 1
   A_r[ i ] = A[ A[i] ]

Outcome A_r = [ 1, 0, 3, 2]

Answer 1

It is possible.

The input array consists of values that are indexes in the same array, and so it is a collection of one or more cycles. Each cycle can have 1 or more elements.

The mutation of the array can best be performed cycle by cycle, as the change in one cycle would only require a temporary storage of one value in that cycle, while the "next" value is copied into the "previous" slot until the whole cycle has been visited and the temporary value can be put in the last slot.

One of the things to consider is that after a cycle has mutated like that, it might not result in a cycle of the same length. For instance, if a cycle has length 4, then the mutation will result in 2 cycles of 2 values. More generally, a cycle with even length will divide into two cycles. Odd cycles keep their length, and just have their order changed.

Once a cycle has mutated, the algorithm should never revisit any of its values "accidentally" applying the mutation to that cycle again.

One way to ensure that this does not happen is to only apply the mutation to a cycle when its rightmost element is visited in a left-to-right iteration. This is the key of the proposed algorithm. That way one can be sure that the elements in this cycle will never be visited again, and will not be mutated again.

Here is an implementation in JavaScript. You can enter the array values in an input field. The algorithm is executed at every change to the input:

function arrange(a) {
    function isRightmostOfCycle(i) {
        let j = a[i]
        while (j < i) j = a[j]
        return j == i
    }

    function updateCycle(i) {
        let saved = a[i]
        let k = i
        for (let j = a[i]; j < i; j = a[j]) {
            a[k] = a[j]
            k = j
        }
        a[k] = saved
    }

    for (let i = 0; i < a.length; i++) {
        if (isRightmostOfCycle(i)) updateCycle(i)
    }
    return a
}

// I/O handling
let input = document.querySelector("input")
let output = document.querySelector("pre");
(input.oninput = function () {
    let a = (input.value.match(/\d+/g) || []).map(Number)
    // Check whether input is valid
    let i = a.findIndex((_,i) => !a.includes(i))
    output.textContent = i < 0 ? arrange(a) : "Missing " + i
})();

input { width: 100% }

Array values: <input value="2,0,5,7,6,4,1,8,3"><p>
Result: 
<pre></pre>

The check whether an index represents the rightmost element of a cycle has a time complexity of O(n), so the total time complexity is O(n²). The additional space complexity however is constant.

Answer 2

It is indeed possible if we combine hole based chain swaps and that we can regonize a cycle in the permutation by the lowest or highest position in the array. We simply for each position only chain through the cycle if the position we are looking at is the highest in that cycle. The hole based method ensure that we only use constant space to perform the rotation of the cycle. The downside is that the time complexity becomes O(n^2). Here is a simple python implementation:

def is_start(array, index):
    start = index
    index = array[index]
    while start > index:
        index = array[index]
    return start == index


def rotate(array, index):
    start = index
    next = array[index]
    hole = next
    while start > next:
        array[index] = array[next]
        index = next
        next = array[index]
    array[index] = hole


def rearrange(array):
    for index in range(len(array)):
        if is_start(array, index):
            rotate(array, index)

Bug-fix

(@trincot) pointed out that using the last entry of the cycle instead of the first ensures that we never investigate possibly corrupted cycles. Effect: Changing the dirrection of inequalities from start < index to start > index.