是否有可能对一个具有恒定额外空间的数组进行逆变?

Let's say I have an array A with n unique elements on the range [0, n). In other words, I have a permutation of the integers [0, n).

假设我有一个数组A有n个唯一的元素在这个范围[0,n)，换句话说，我有一个整数的排列[0,n]。

Is possible to transform A into B using O(1) extra space (AKA in-place) such that B[A[i]] = i?

是否可以使用O(1)额外的空间(也就是in-place)将A转换成B，使B[A[i]] = i?

For example:

例如:

       A                  B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]

2 个解决方案

#1

Yes, it is possible, with O(n^2) time algorithm:

是的,这是可能的,与O(n ^ 2)时间算法:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0. This is cycle leader algorithm.

取索引0处的元素，然后将0写入该元素索引的单元格中。然后使用重写元素获取下一个索引，并在那里写入先前的索引。继续，直到回到索引0。这是循环前导算法。

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from this index. If this cycle contains any index below the starting index, just skip it.

然后从索引1、2、…但是在做任何更改之前，执行循环前导算法，而不需要从这个索引开始进行任何修改。如果这个循环包含起始索引以下的任何索引，就跳过它。

Or this O(n^3) time algorithm:

或者这个O(n ^ 3)时间算法:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0.

取索引0处的元素，然后将0写入该元素索引的单元格中。然后使用重写元素获取下一个索引，并在那里写入先前的索引。继续，直到返回索引0。

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from all preceding indexes. If current index is present in any preceding cycle, just skip it.

然后从索引1、2、…但是在做任何更改之前，执行循环前导算法，不需要从所有前面的索引开始进行任何修改。如果当前索引出现在任何一个周期中，就跳过它。

I have written (slightly optimized) implementation of O(n^2) algorithm in C++11 to determine how many additional accesses are needed for each element on average if random permutation is inverted. Here are the results:

我写了(略)优化实现O(n ^ 2)算法的c++ 11确定需要多少额外的访问每个元素平均随机排列是否倒。这里是结果:

size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617

While size grows exponentially, number of element accesses grows almost linearly, so expected time complexity for random permutations is something like O(n log n).

当大小成指数增长时，元素访问的数量几乎是线性增长的，所以随机排列的预期时间复杂度是O(n log n)。

#2

Inverting an array A requires us to find a permutation B which fulfills the requirement A[B[i]] == i for all i.

逆变一个数组A需要我们找到一个满足A[B[i]] = i的置换B。

To build the inverse in-place, we have to swap elements and indices by setting A[A[i]] = i for each element A[i]. Obviously, if we would simply iterate through A and perform aforementioned replacement, we might override upcoming elements in A and our computation would fail.

要构建反向的就地，我们必须通过设置[i] = i来交换元素和索引[i]。显然，如果我们只是遍历A并执行前面提到的替换，我们可能会覆盖A中即将出现的元素，那么我们的计算就会失败。

Therefore, we have to swap elements and indices along cycles of A by following c = A[c] until we reach our cycle's starting index c = i.

因此，我们必须遵循c = A[c]，沿着A的周期交换元素和指标，直到达到循环的起始索引c = i。

Every element of A belongs to one such cycle. Since we have no space to store whether or not an element A[i] has already been processed and needs to be skipped, we have to follow its cycle: If we reach an index c < i we would know that this element is part of a previously processed cycle.

A的每个元素都属于这样一个循环。由于我们没有空间来存储元素A[i]是否已经被处理并需要跳过，所以我们必须遵循它的循环:如果我们到达索引c < i，我们就知道这个元素是先前处理过的循环的一部分。

This algorithm has a worst-case run-time complexity of O(n²), an average run-time complexity of O(n log n) and a best-case run-time complexity of O(n).

这个算法有一个坏的运行时的复杂性O(n²),平均运行时的复杂性O(n log n)和最佳运行时O(n)的复杂性。

function invert(array) {
  main:
  for (var i = 0, length = array.length; i < length; ++i) {
    
    // check if this cycle has already been traversed before:
    for (var c = array[i]; c != i; c = array[c]) {
      if (c <= i) continue main;
    }
    
    // Replacing each cycle element with its predecessors index:
    var c_index = i, 
        c = array[i];
    do {
      var tmp = array[c];
      array[c] = c_index; // replace
      c_index = c; // move forward
      c = tmp;
    } while (i != c_index)
      
  }
  return array;
}
  
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]

Example for A = [1, 2, 3, 0] :

例如A = [1,2,3,0]:

The first element 1 at index 0 belongs to the cycle of elements 1 - 2 - 3 - 0. Once we shift indices 0, 1, 2 and 3 along this cycle, we have completed the first step.

索引0处的第一个元素1属于元素1 - 2 - 3 - 0的循环。一旦我们沿着这个循环移位了0、1、2和3，我们就完成了第一步。
The next element 0 at index 1 belongs to the same cycle and our check tells us so in only one step (since it is a backwards step).

索引1处的下一个元素0属于同一个循环，我们的检查只告诉我们一个步骤(因为它是一个后退)。
The same holds for the remaining elements 1 and 2.

其余的元素1和2也是如此。

In total, we perform 4 + 1 + 1 + 1 'operations'. This is the best-case scenario.

总的来说，我们执行4 + 1 + 1 + 1的“操作”。这是最好的情况。

#1