arrays - 仅使用交换改变数组顺序

Question

假设您有两个数组，a 和 b。 a 的数据对你是完全隐藏的。您可以对 a 执行的唯一操作是交换两个元素。 b 的数据完全公开且可变。

b 在位置 i 的值指示存储在 a[i] 中的值的目的地。也就是说，如果 b[3] = 7，我们希望将 a[3] 中的值移动到 a[7] 中。我正在尝试编写一种算法，该算法根据数组 b 中的信息对数组 a 进行变异，仅使用 a 上的交换操作(最好是线性时间和常数空间)。举个例子:

if   a  = { a b c d e f }
and  b  = { 1 3 2 0 5 4 }
then a' = { d a c b f e }
(ie, a[i] = a'[b[i]])

我尝试了一种天真的方法，即遍历 b 并愉快地执行 a.Swap(i, b[i])，同时一直吹口哨，但最终会覆盖自身并移动已经在正确位置的数据地点(正如您可能猜到的那样)。

编辑:这确实必须是线性时间。它用于并行排序算法，因此速度至关重要。

Answer 1

Go 中的解决方案:

for i := 0; i != len(b); i++ {
    for b[i] != i {
        a.Swap(i, b[i])
        b.Swap(i, b[i])
    }
}

这可能不会立即看起来 O(n)，但请注意

• 每个 a.Swap() 都会将 a 的至少一个元素放入其最终位置
  • 一旦一个元素到达它的最终位置，它就再也不会被交换
  • 所以最多有n次交换
• b[i] != i 测试对每个交换进行一次，每个 i 进行一次额外时间
  • 所以最多有2n个测试

如您所见，此算法在时间上为 O(n)，在空间上为 O(1)。