根據指數向量對向量進行重新排序 - 更新

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); 
}