Wie erhalten Sie die Indexpermutation nach der Sortierung

Question

Gegeben ein Array arr = {5, 16, 4, 7}, können wir es durch sort(arr, arr+sizeof(arr)/sizeof(arr[0])) sortieren. so jetzt das Array arr = {4, 5, 7, 16} und der Permutationsindex für das sortierte Array ist {2, 0, 3, 1}. Mit anderen Worten, das arr[2] im ursprünglichen Array ist jetzt das kleinste Element im sortierten Array in Position 0.

Gibt es einen effizienten Weg, um den Permutationsindex zu erhalten?

Vielen Dank

Answer 1

Erstellen Sie ein Array von Indizes, füllen Sie es mit den Zahlen 0..N-1, und sortieren Sie es mit einem benutzerdefinierten Vergleicher. Der Komparator sollte Elemente aus dem ursprünglichen Array bei den Indizes lhs und rhs vergleichen. Sortieren der Anordnung von Indizes auf diese Weise sie als eine Permutation Nachbestellungen:

vector<int> data = {5, 16, 4, 7}; 
vector<int> index(data.size(), 0); 
for (int i = 0 ; i != index.size() ; i++) { 
    index[i] = i; 
} 
sort(index.begin(), index.end(), 
    [&](const int& a, const int& b) { 
     return (data[a] < data[b]); 
    } 
); 
for (int i = 0 ; i != index.size() ; i++) { 
    cout << index[i] << endl; 
} 

Dieser druckt 2, 0, 3, 1

Hier ist ein demo on ideone.

Hinweis: Sie index verwenden können die data in sortierter Reihenfolge abzurufen:

for (int i = 0 ; i != index.size() ; i++) { 
    cout << data[index[i]] << endl; 
} 

Answer 2

Warum nicht einige Satellitendaten? Anstatt die Zahlen zu sortieren, sortieren Sie einfach Zahlenpaare und ihre Indizes. Da die Sortierung zuerst an dem ersten Element des Paares vorgenommen wird, sollte dies keinen stabilen Sortieralgorithmus stören.

Bei instabilen Algorithmen wird dies zu einem stabilen Algorithmus geändert.

Beachten Sie jedoch, dass wenn Sie versuchen, auf diese Weise zu sortieren, der Index beim Sortieren generiert wird, nicht danach.

Da die Kenntnis des Permutationsindex zu einem O (n) -Sortieralgorithmus führen würde, können Sie es nicht schneller als O (nlogn) machen.

Answer 3

Ja, es ist eine mit O(NlogN) time.Since die Sortierung ohnehin O(NlogN) Zeit in Anspruch nimmt, wird dies nicht Gesamtzeitkomplexität beeinflussen.
Zeitkomplexität: O(NlogN)
Platzkomplexität: O(N)
wo N = Anzahl der Elemente im Eingabearray

Algorithmus:

1. Make Kopie des Eingangsfeldes (P) Nennen Sie es Q.
2. Sor t Eingangsarray P.
3. Für jede Zahl in Q, tut binären Suchindex dieses Elements zu finden in P.

Answer 4

Nun, in C++ können wir Paar Datentypen verwenden, um dies einfach zu tun. Beispielcode unten;

arr = {5, 16, 4, 7}; 
vector<pair<int,int> >V; 
for(int i=0;i<4;i++){ 
    pair<int,int>P=make_pair(arr[i],i); 
    V.push_back(P); 
} 

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

Also V [i].der erste ist der i-te Wert und V [i] .zweit ist der i-te Index. So drucken Sie den Index im sortierten Array.

Beachten Sie, dass beim Sortieren eines Arrays (oder Vektors) von Paarelementen das Array zuerst anhand der ersten Werte sortiert wird. Wenn zwei Paare denselben ersten Wert haben, werden sie basierend auf ihrem zweiten Wert sortiert.

Answer 5

Multimap zur Rettung kommen kann

template<typename TIn, typename TOut> 
sortindex(const TIn &first, const TIn &last, TOut &out) { 
    using ValT = typename std::decay<decltype(*first)>::type; 
    std::multimap<ValT, size_t> sindex; 

    for(auto p=first; p != last; p++) 
     sindex.emplace(*p, std::distance(first, p)); 

    for(auto &&p: sindex) 
     *out++ = p.second; 
} 

, die wie folgt verwendet werden kann:

std::vector<size_t> a{32, 22, 45, 9, 12, 15}; 
std::vector<size_t> indexes; 

sortindex(a.begin(), a.end(), std::back_inserter(indexes)); 

Wenn eine Kopplung zwischen den sortierten Werten und dem Index müsste sein, dann kann der multimap sein direkt zurückgegeben, anstatt die Indizes in den Ausgabe-Iterator zu schreiben.

template<typename TIn> 
auto 
sortindex(const TIn &first, const TIn &last) 
    --> std::multimap<typename std::decay<decltype(*first)>::type, size_t> 
{ // return value can be commented out in C++14 
    using ValT = typename std::decay<decltype(*first)>::type; 
    std::multimap<ValT, size_t> sindex; 

    for(auto p=first; p != last; p++) 
     sindex.emplace(*p, std::distance(first, p)); 

    return sindex; 
} 

Answer 6

Ich musste vor kurzem ein ähnliches Problem in PHP lösen. Sie erstellen eine lokale Vergleichsfunktion, die von PHPs UASORT-Sortieralgorithmus verwendet wird. Rufen Sie array_keys() für das sortierte Array auf, und das sollte Ihr Permutationsarray ausspeien.

// Testarray

$ tarray = array ('2', '10', '1', '23', '8', '3');

// Array sortieren; Um die Indexzuordnung beizubehalten, verwenden Sie uasort; Verwenden Sie sonst usort usw.

uasort ($ tArray, 'compareSize');

// die resultierenden Schlüssel sind Ihre Permutation Indizes (falls uasort in vorherigen Schritt verwendet)

$ Keys = array_keys ($ tarray);

// lokale Funktion

Funktion compareSize ($ a, $ b) {

if ($ a == $ b) Vergleichen {return 0; } else {return ($ a < $ b)? -1: 1; }

}

======================================== =========================== Ergebnisse:

sortierte =: Array ([2] => 1 [ 0] => 2 [5] => 3 [4] => 8 [1] => 10 [3] => 23)

keys =: Array ([0] => 2 [1] => 0 [2] => 5 [3] => 4 [4] => 1 [5] => 3)

Answer 7

Ich denke, wir können dieses Problem lösen, ohne Vektor zu verwenden. Ich bin Neuling, um ehrlich zu sein, ich verstehe nicht, was Sie oben geschrieben habe, und alle von Ihnen verwendeten Vektors, die ich später studieren :))) (i faul bin) Hier ist meine Art und Weise:

// Zuerst Kopie Array a [] zu Array b []

void copyarray(double b[],double a[],int n){ 
    for(int i=0;i<n;i++)b[i]=a[i]; 
    } 

// Zweitens sortieren Array a [] (Abnahme)

/* Drittens "Sortierer" Array a [], dass bedeutet: in Array a [], wenn es die gleichen Werte gibt, werden sie zu einem verschmelzen! wird i-Array festgelegt o [] ist "die sortierten Array a []" */

void sorter(double o[],double a[],int n,int &dem){ 
    int i; 
    o[0]=a[0]; 
    for(i=1;i<n;i++){ 
     if(a[i]!=a[i-1]){ 
      dem++; o[dem]=a[i]; 
     } 
     } 
     dem++; 
} 

/* 4., unser Hauptziel: das Index: i den Index in Array setzen c [] */

void index_sort(double o[],double b[], double c[], int dem, int n){ 
    int i,j,chiso=0; 
    for(j=0;j<dem;j++){ 
     for(i=0;i<n;i++){ 
      if(b[i]==o[j]){ 
      c[chiso]=i; 
      chiso++; 
      } 
     } 
    } 
} 

    // DONE! 
int main(){ 
     int n,dem=0; 
     double a[100],b[100],c[100],o[100]; 
     cin>>n; 
     input(a,n); 
     copyarray(b,a,n); 
     copyarray(c,a,n); 
     sort(a,n); 
     sorter(o,a,n,dem); 
     index_sort(o,b,c,dem,n); 
     for(int i=0;i<n;i++) cout<<c[i]<<" "; 
    }