C++ sortowanie i śledzenie indeksów

Question

Używając C++, i mam nadzieję, że biblioteka standardowa, chcę posortować sekwencję próbek w porządku rosnącym, ale chcę też zapamiętać oryginalne indeksy nowo próbek.

Na przykład mam zestaw, wektor lub macierz próbek A : [5, 2, 1, 4, 3]. Chcę je posortować na: B : [1,2,3,4,5], ale chcę też zapamiętać oryginalne indeksy wartości, więc mogę uzyskać inny zestaw, który będzie: C : [2, 1, 4, 3, 0 ] - który odpowiada indeksowi każdego elementu w 'B', oryginalny "A".

Na przykład w Matlab można zrobić:

[a,b]=sort([5, 8, 7]) 
a = 5 7 8 
b = 1 3 2 

Czy ktoś może zobaczyć dobry sposób to zrobić?

Answer 1

Jeśli jest to możliwe, można zbudować tablicę pozycji za pomocą funkcji find, a następnie posortować tablicę.

Albo można użyć mapę, gdzie klucz byłby element, a wartości listę swojej pozycji w kolejnych macierzy (A, B i C)

Zależy później używa tej macierzy .

Answer 2

Czy elementy w wektorze są unikatowe? Jeśli tak, skopiuj wektor, posortuj jedną z kopii za pomocą STL Sort, a następnie znajdź indeks każdego elementu w oryginalnym wektorze.

Jeśli wektor ma obsługiwać zduplikowane elementy, myślę, że lepiej jest wprowadzić własną procedurę sortowania.

Answer 3

Można sortować std :: pair zamiast tylko ints - pierwsze int to oryginalne dane, drugie int to oryginalny indeks. Następnie podaj komparator, który sortuje tylko na pierwszej int. Przykład:

Your problem instance: v = [5 7 8] 
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>] 

Sortuj nowa instancja problemu za pomocą komparatora jak:

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 

Wynikiem std :: sort na v_prime, przy użyciu tego komparatora, powinno być:

v_prime = [<5,0>, <7,2>, <8,1>] 

Możesz usunąć indeksy, przechodząc do wektora, chwytając .second od każdej std :: pair.

Answer 4

Napisałem ogólną wersję sortowania indeksu.

template <class RAIter, class Compare> 
void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp, 
    std::vector<size_t>& indexes) { 

    std::vector< std::pair<size_t,RAIter> > pv ; 
    pv.reserve(iterEnd - iterBegin) ; 

    RAIter iter ; 
    size_t k ; 
    for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) { 
     pv.push_back(std::pair<int,RAIter>(k,iter)) ; 
    } 

    std::sort(pv.begin(), pv.end(), 
     [&comp](const std::pair<size_t,RAIter>& a, const std::pair<size_t,RAIter>& b) -> bool 
     { return comp(*a.second, *b.second) ; }) ; 

    indexes.resize(pv.size()) ; 
    std::transform(pv.begin(), pv.end(), indexes.begin(), 
     [](const std::pair<size_t,RAIter>& a) -> size_t { return a.first ; }) ; 
} 

Użycie jest takie samo jak dla std :: sort z wyjątkiem kontenera indeksu do odbierania posortowanych indeksów. testowanie:

int a[] = { 3, 1, 0, 4 } ; 
std::vector<size_t> indexes ; 
argsort(a, a + sizeof(a)/sizeof(a[0]), std::less<int>(), indexes) ; 
for (size_t i : indexes) printf("%d\n", int(i)) ; 

powinieneś dostać 2 1 0 3. dla kompilatorów C++ 0x bez wsparcia zastąpić wyraz Lamba jako szablon klasy:

template <class RAIter, class Compare> 
class PairComp { 
public: 
    Compare comp ; 
    PairComp(Compare comp_) : comp(comp_) {} 
    bool operator() (const std::pair<size_t,RAIter>& a, 
    const std::pair<size_t,RAIter>& b) const { return comp(*a.second, *b.second) ; }   
} ; 

i przepisać std :: rodzaju jak

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ; 

Answer 5

Korzystanie C++ 11 lambdas

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 
    sort(idx.begin(), idx.end(), 
     [&v](size_t i1, size_t i2) {return v[i1] < v[i2];}); 

    return idx; 
} 

teraz można użyć indeksu wektor zwrócony w iteracji takich jak

for (auto i: sort_indexes(v)) { 
    cout << v[i] << endl; 
} 

Oczywiście, możesz również wybrać dostarczenie własnego oryginalnego wektora indeksu, funkcji sortowania, komparatora lub automatycznie zmienić kolejność v w funkcji sort_indexes za pomocą dodatkowego wektora.

Answer 6

Natknąłem się na to pytanie i zorientowałem się, że bezpośrednie sortowanie iteratorów byłoby sposobem sortowania wartości i śledzenia wskaźników; Nie ma potrzeby definiowania dodatkowego kontenera o wartości (index, index), który jest przydatny, gdy wartości są dużymi obiektami; W iteratory zapewnia dostęp zarówno do wartości i indeksu:

/* 
* a function object that allows to compare 
* the iterators by the value they point to 
*/ 
template < class RAIter, class Compare > 
class IterSortComp 
{ 
    public: 
     IterSortComp (Compare comp): m_comp (comp) { } 
     inline bool operator() (const RAIter & i, const RAIter & j) const 
     { 
      return m_comp (* i, * j); 
     } 
    private: 
     const Compare m_comp; 
}; 

template <class INIter, class RAIter, class Compare> 
void itersort (INIter first, INIter last, std::vector <RAIter> & idx, Compare comp) 
{ 
    idx.resize (std::distance (first, last)); 
    for (typename std::vector <RAIter>::iterator j = idx.begin(); first != last; ++ j, ++ first) 
     * j = first; 

    std::sort (idx.begin(), idx.end(), IterSortComp< RAIter, Compare > (comp)); 
} 

jak na przykład zastosowania:

std::vector <int> A (n); 

// populate A with some random values 
std::generate (A.begin(), A.end(), rand); 

std::vector < std::vector <int>::const_iterator > idx; 
itersort (A.begin(), A.end(), idx, std::less <int> ()); 

się, na przykład, 5. najmniejszy element sortowanej wektora będzie stanowił **idx[ 5 ] a jego indeksem w oryginalnym wektorze byłby distance(A.begin(), *idx[ 5 ]) lub po prostu *idx[ 5 ] - A.begin().

Answer 7

Zrób std::pair w funkcji następnie posortować pary:

wersja ogólna:

template< class RandomAccessIterator,class Compare > 
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) -> 
    std::vector<std::pair<std::uint32_t,RandomAccessIterator>> 
{ 
    using valueType=typename std::iterator_traits<RandomAccessIterator>::value_type; 
    using Pair=std::pair<std::uint32_t,RandomAccessIterator>; 

    std::vector<Pair> index_pair; 
    index_pair.reserve(std::distance(begin,end)); 

    for(uint32_t idx=0;begin!=end;++begin,++idx){ 
     index_pair.push_back(Pair(idx,begin)); 
    } 

    std::sort(index_pair.begin(),index_pair.end(),[&](const Pair& lhs,const Pair& rhs){ 
      return cmp(*lhs.second,*rhs.second); 
    }); 

    return index_pair; 
} 

ideone

Answer 8

Nie ma innego sposobu, aby rozwiązać ten problem, za pomocą mapy:

vector<double> v = {...}; // input data 
map<double, unsigned> m; // mapping from value to its index 
for (auto it = v.begin(); it != v.end(); ++it) 
    m[*it] = it - v.begin(); 

Wyeliminuje to jednak elementy nieunikalne. Jeśli to nie do przyjęcia, należy użyć multimap:

vector<double> v = {...}; // input data 
multimap<double, unsigned> m; // mapping from value to its index 
for (auto it = v.begin(); it != v.end(); ++it) 
    m.insert(make_pair(*it, it - v.begin())); 

W celu wyjścia indeksy, iteracyjne nad mapą lub multimapy:

for (auto it = m.begin(); it != m.end(); ++it) 
    cout << it->second << endl; 

Answer 9

Cóż, moje rozwiązanie wykorzystuje technikę pozostałości. Możemy umieścić wartości pod sortowania w górnych 2 bajty i indeksów elementów - w dolnych 2 bajty:

int myints[] = {32,71,12,45,26,80,53,33}; 

for (int i = 0; i < 8; i++) 
    myints[i] = myints[i]*(1 << 16) + i; 

Następnie posortować tablicę myints jak zwykle:

std::vector<int> myvector(myints, myints+8); 
sort(myvector.begin(), myvector.begin()+8, std::less<int>()); 

Po tym może uzyskać dostęp do wskaźników elementów za pomocą residuum.Poniższy kod drukuje indeksy wartości posortowanych w kolejności rosnącej:

for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) 
    std::cout << ' ' << (*it)%(1 << 16); 

Oczywiście, technika ta działa tylko dla stosunkowo małych wartościach w oryginalnej tablicy myints (czyli te, które pasują do górnych 2 bajty int). Ale ma dodatkową zaletę polegającą na rozróżnianiu identycznych wartości myints: ich indeksy zostaną wydrukowane we właściwej kolejności.

Answer 10

Dla tego typu pytania Przechowuj dane macierzy orignal do nowych danych, a następnie przeszukuj binarnie pierwszy element posortowanej tablicy w zduplikowanej tablicy i to indice powinny być przechowywane w wektorze lub tablicy.

input array=>a 
duplicate array=>b 
vector=>c(Stores the indices(position) of the orignal array 
Syntax: 
for(i=0;i<n;i++) 
c.push_back(binarysearch(b,n,a[i]));` 

Tutaj binarysearch jest funkcją, która przyjmuje tablicę, rozmiar tablicy, szukając pozycji i wróci pozycję szukanego elementu

Answer 11

jej łatwiej niż się wydaje.

Załóżmy dany wektor jest

A=[2,4,3] 

utworzyć nowy wektor

V=[0,1,2] // indicating positions 

Sortuj V i podczas sortowania zamiast porównując elementy V porównać odpowiadające elementy

//Assume A is a given vector with N elements 
vector<int> V(N); 
int j=0; 
std::iota(V.begin(),V.end(),j++); //Initializing 
for(int i=0;i<N;i++) 
     V[i]=i; 
sort(V.begin(),V.end(), [&](int x,int y){return A[x]<A[y];}); 

Answer 12

vector<pair<int,int> >a; 

for (i = 0 ;i < n ; i++) { 
    // filling the original array 
    cin >> k; 
    a.push_back (make_pair (k,i)); // k = value, i = original index 
} 

sort (a.begin(),a.end()); 

for (i = 0 ; i < n ; i++){ 
    cout << a[i].first << " " << a[i].second << "\n"; 
} 

Teraz a zawiera zarówno nasze wartości, jak i ich odpowiednie indeksy w posortowanym.

przy i "th.

a[i].second = idx w początkowej tablicy.

Answer 13

Piękne rozwiązanie autorstwa @Lukasz Wiklendt! Chociaż w moim przypadku potrzebowałem czegoś bardziej ogólny, więc to trochę zmodyfikowane:

template <class RAIter, class Compare> 
vector<size_t> argSort(RAIter first, RAIter last, Compare comp) { 

    vector<size_t> idx(last-first); 
    iota(idx.begin(), idx.end(), 0); 

    auto idxComp = [&first,comp](size_t i1, size_t i2) { 
     return comp(first[i1], first[i2]); 
    }; 

    sort(idx.begin(), idx.end(), idxComp); 

    return idx; 
} 

Przykład: Znajdź indeksy sortowania wektor ciągów według długości, z wyjątkiem pierwszego elementu, który jest obojętne.

vector<string> test = {"dummy", "a", "abc", "ab"}; 

auto comp = [](const string &a, const string& b) { 
    return a.length() > b.length(); 
}; 

const auto& beginIt = test.begin() + 1; 
vector<size_t> ind = argSort(beginIt, test.end(), comp); 

for(auto i : ind) 
    cout << beginIt[i] << endl; 

drukuje:

abc 
ab 
a