使用C++ (希望还有标准库),我希望按升序对一系列样本进行排序,但我还希望记住新样本的原始索引。
例如,我有一个集合,或向量,或样本矩阵A : [5, 2, 1, 4, 3]
。我想要将这些元素排序为B : [1,2,3,4,5]
,但我也想记住这些值的原始索引,这样我就可以获得另一个集合:C : [2, 1, 4, 3, 0 ]
-它对应于原始'A‘中'B’中每个元素的索引。
例如,在Matlab中,您可以执行以下操作:
[a,b]=sort([5, 8, 7])
a = 5 7 8
b = 1 3 2
有没有人能找到一种好的方法呢?
发布于 2012-09-13 12:10:42
使用C++
11 lambdas:
#include <iostream>
#include <vector>
#include <numeric> // std::iota
#include <algorithm> // std::sort, std::stable_sort
using namespace std;
template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {
// initialize original index locations
vector<size_t> idx(v.size());
iota(idx.begin(), idx.end(), 0);
// sort indexes based on comparing values in v
// using std::stable_sort instead of std::sort
// to avoid unnecessary index re-orderings
// when v contains elements of equal values
stable_sort(idx.begin(), idx.end(),
[&v](size_t i1, size_t i2) {return v[i1] < v[i2];});
return idx;
}
现在,您可以在迭代中使用返回的索引向量,例如
for (auto i: sort_indexes(v)) {
cout << v[i] << endl;
}
您还可以选择提供原始索引向量、排序函数、比较器,或者使用额外的向量在sort_indexes函数中自动重新排序v。
发布于 2009-10-16 11:53:11
你可以对std::pair进行排序,而不仅仅是int --第一个int是原始数据,第二个int是原始索引。然后提供一个只对第一个int进行排序的比较器。示例:
Your problem instance: v = [5 7 8]
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]
使用比较器对新问题实例进行排序,例如:
typedef std::pair<int,int> mypair;
bool comparator ( const mypair& l, const mypair& r)
{ return l.first < r.first; }
// forgetting the syntax here but intent is clear enough
使用该比较器对v_prime执行std::sort的结果应该是:
v_prime = [<5,0>, <7,2>, <8,1>]
您可以通过遍历向量,从每个std::对中抓取.second来剥离索引。
发布于 2016-10-22 03:06:58
假设给定的向量是
A=[2,4,3]
创建一个新矢量
V=[0,1,2] // indicating positions
排序V和排序时,不比较V的元素,而是比较A的相应元素
//Assume A is a given vector with N elements
vector<int> V(N);
std::iota(V.begin(),V.end(),0); //Initializing
sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );
https://stackoverflow.com/questions/1577475
复制相似问题