根据指数向量对向量进行重新排序 - 更新

Question

这是对previous question about reordering in place的更新关于向量的索引存在一些混淆。调用要重新排列的矢量vA和指数vI的矢量，则应按照vA [vI [0]]，vA [vI [1]]，vA [vI [2] ...的顺序对vA进行重新排序。 。一个示例用法是将vI初始化为一组vA.size（）索引，0到vA.size（） - 1，然后根据vA对vI进行排序（使用vA [vI [...]]进行比较）。然后重新排序功能可以用来根据vI对vA进行排序。

考虑初始vA作为排序vA的置换。在根据vA对vI进行排序之后，然后根据vI“unpermutes”vA将vA重新排序以排序排列。通过下面显示的示例函数，对vA进行重新排序也会将vI重新排列为初始化状态（0到vA.size（） - 1）。

Answer 1

移动数据而不是交换数据的工作重新排序的版本。这个例子可能更容易解释。每个排列都是一组“循环”。通过撤销周期重新排序工作。假设有8个元素，并且vI包含所需的顺序。我把我的索引以上VI：

i :  { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } 

vI[i] = { 5 , 7 , 0 , 3 , 6 , 2 , 4 , 1 } 

周期1：VI [0] == 5，VI [5] == 2，VI [2] == 0

周期2：六[1] == 7，VI [7] == 1

循环3：VI [3] == 3.

循环4：VI [4] == 6，VI [6] = = 0

撤销循环1，t = vA [0]，vA [0] = vA [5]，vA [5] = vA [2]，vA [2] = t。

撤消循环2，t = vA [1]，vA [1] = vA [7]，vA [7] = t。

撤消周期3，不进行校正所需

撤消周期4，T = vA型[4]，VA [4] = vA型[6]，VA [6] =吨。

每次将值存储在vA [k]中时，vI [k]被设置为k以指示vA [k]被排序。

template <class T> 
void reorder(vector<T>& vA, vector<size_t>& vI) 
{ 
size_t i, j, k; 
T t; 
    for(i = 0; i < vA.size(); i++){ 
     if(i != vI[i]){ 
      t = vA[i]; 
      k = i; 
      while(i != (j = vI[k])){ 
      // every move places a value in it's final location 
       vA[k] = vA[j]; 
       vI[k] = k; 
       k = j; 
      } 
      vA[k] = t; 
      vI[k] = k; 
     } 
    } 
} 

Answer 2

下面的例子显示了reorderfail（）的一个非工作版本，后跟一个名为reorder（）的工作版本。这两个函数都会将vI返回到原始状态0到vA.size（） - 1，但reorderfail（）无法正确重新安排vA，因为它缺少“取消注册”vA所需的间接级别。

#include <algorithm> 
#include <vector> 

using namespace std; 

template <class T> 
void reorderfail(vector<T>& vA, vector<size_t>& vI) 
{ 
size_t i, j; 
    for(i = 0; i < vA.size(); i++){ 
     while(i != (j = vI[i])){ 
      swap(vA[i], vA[j]); 
      swap(vI[i], vI[j]); 
     } 
    } 
} 

template <class T> 
void reorder(vector<T>& vA, vector<size_t>& vI) 
{ 
size_t i, j, k; 
    for(i = 0; i < vA.size(); i++){ 
     while(i != (j = vI[i])){ 
      k = vI[j]; 
      swap(vA[j], vA[k]); 
      swap(vI[i], vI[j]); 
     } 
    } 
} 

int main() 
{ 
char A[] = { 'b', 'c', 'a' }; 
size_t I[] = { 2 , 0 , 1 }; // order should be A[2] A[0] A[1] 
size_t size = sizeof(A)/sizeof(*A); 

    vector<char> vA(size); 
    vector<size_t> vI(size); 

    vA.assign(A, A + size); 
    vI.assign(I, I + size); 
    reorderfail(vA, vI); // returns vA = {'c', 'a', 'b'}; 

    vA.assign(A, A + size); 
    vI.assign(I, I + size); 
    reorder(vA, vI);  // returns vA = {'a', 'b', 'c'}; 

    return(0); 
}