就地阵列重新排序？

Question

假设我有一个a长度数组n和第二个数组indices,也是长度数组n. indices包含序列的一些任意排列[0, n).我想重新排列a,使其按照指定的顺序排列indices.例如,使用D语法:

auto a = [8, 6, 7, 5, 3, 0, 9];
auto indices = [3, 6, 2, 4, 0, 1, 5];
reindexInPlace(a, indices);
assert(a == [5, 9, 7, 3, 8, 6, 0]);

这可以在O(1)空间和O(n)时间内完成,最好不要变异indices吗？

Answer 1

随着变异indices:(.没有看起来很难(见稳定的就地mergesort).

a = [8, 6, 7, 5, 3, 0, 9]
indices = [3, 6, 2, 4, 0, 1, 5]

for i in xrange(len(a)):
    x = a[i]
    j = i
    while True:
        k = indices[j]
        indices[j] = j
        if k == i:
            break
        a[j] = a[k]
        j = k
    a[j] = x

print a

Answer 2

这就是我称之为"permute from"算法.在类C语言中,它看起来如下

  for (i_dst_first = 0; i_dst_first < n; ++i_dst_first)
  {
    /* Check if this element needs to be permuted */

    i_src = indices[i_dst_first];
    assert(i_src < n);
    if (i_src == i_dst_first)
      /* This element is already in place */
      continue;

    i_dst = i_dst_first;
    pending = a[i_dst];

    /* Follow the permutation cycle */

    do
    {
      a[i_dst] = a[i_src];
      indices[i_dst] = i_dst;

      i_dst = i_src;
      i_src = indices[i_src];
      assert(i_src != i_dst);

    } while (i_src != i_dst_first);

    a[i_dst] = pending;
    indices[i_dst] = i_dst;
  }

请注意,此算法会破坏index阵列.我将其称为"permute from",因为该index[i]值指定了从哪里获取结果序列的第i个元素.

还要注意,序列的就地置换所需的"元素移动"操作的数量等于number of misplaced elements+ number of cycles in the permutation.该算法实现了这个限制,因此就移动次数而言,没有更好的算法是可能的.

该算法的潜在问题在于它基于"杂耍"方法,使其缓存行为远非最佳.因此,虽然这个算法在理论上是最好的算法,但它在现实生活中可能会失去一些更"实用"的算法.

还可以实现"置换到"算法,其中index[i]值指定重新定位原始第i个元素的位置.