是否可以重新排列具有恒定内存开销的数组？

Question

我在阅读一些 Whosebug 问题时偶然发现了这个问题，但找不到令人满意的答案。

假设我们有一个长度为 n 的 array A，它以随机方式包含从 0 到 n-1 的索引。是否可以重新排列数组，使其结果为 A[ A[i] ]，内存开销为常量 O(1)？

示例：

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

如果可能的话，算法的概述会很好。否则解释为什么不可能。由于就地排序是一回事，因此可能效果相似。

澄清：如果您没有内存限制，则该算法很简单：

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

结果A_r = [ 1, 0, 3, 2]

Answer 1

如果我们结合基于空洞的链交换并且我们可以通过数组中的最低或最高位置重新排列排列中的循环，这确实是可能的。如果我们正在查看的位置是该循环中的最高位置，我们只需为每个位置仅链接整个循环。基于孔的方法确保我们只使用常数 space 来执行循环的旋转。缺点是时间复杂度变成O(n^2)。这是一个简单的 python 实现：

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.

Answer 2

有可能。

输入数组由作为同一数组索引的值组成，因此它是一个或多个循环的集合。每个循环可以有 1 个或多个元素。

数组的变异最好逐个循环执行，因为一个循环的变化只需要在该循环中临时存储一个值，而"next"值被复制到"previous" slot直到整个循环都被访问过，临时值可以放在最后一个slot中。

需要考虑的一件事是，在一个循环发生这样的突变之后，它可能不会产生相同长度的循环。例如，如果一个循环的长度为 4，则突变将导致 2 个循环的 2 个值。更一般地，一个长度为偶数的循环将分成两个循环。奇数循环保持其长度，只是改变了它们的顺序。

一旦一个循环发生变异，算法就永远不会重新访问它的任何值"accidentally"再次将变异应用于该循环。

确保这种情况不会发生的一种方法是仅在 最右边 元素在 left-to-right 迭代中被访问时才将突变应用于循环。这是所提出算法的关键。这样就可以确定这个循环中的元素永远不会被再次访问，也不会再次发生变异。

这是 JavaScript 中的一个实现。您可以在输入字段中输入数组值。该算法在每次输入更改时执行：

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>

检查一个索引是否代表循环最右边的元素，时间复杂度为O(n)，所以总时间复杂度为O( n²)。然而，额外的 space 复杂性是不变的。

是否可以重新排列具有恒定内存开销的数组？

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

arrays

algorithm

in-place

Bug-fix