Finden Reihenfolge eines Arrays mit minimalen Speicher und Zeit

Question

Sagen wir, ich habe ein Array von 5 Elementen. Mein Programm weiß, dass es immer 5 Elemente gibt und wenn es sortiert ist, ist es immer nur 1,2,3,4,5.

Nach Permutationsformel, d. H. N!/(N-r)! Wir können es auf 120 Arten bestellen.

In C++ mit Std :: Next_Permutation kann ich alle diese 120 Bestellungen generieren.

Nun akzeptiert mein Programm/Routine ein Eingabeargument als eine Zahl im Bereich von 1 bis 120 und gibt die spezifische Reihenfolge eines Arrays als Ausgabe.

Dies funktioniert gut für kleine Array-Größen, wie ich std :: next_permutation wiederholen kann, bis das Input-Parameter übereinstimmt.

Das eigentliche Problem ist, wie kann ich es in weniger Zeit tun, wenn mein Array 25 Elemente oder mehr hat? Für 25 Elemente ist die Anzahl der möglichen Aufträge: 15511210043330985984000000.

Gibt es eine Technik, die ich leicht finden kann die Reihenfolge der Zahlen mit einer bestimmten Nummer als Eingabe?

Vielen Dank im Voraus :)

Answer 1

Dies ist ein Beispiel C++ Implementierung des Algorithmus in this link erwähnt:

#include <vector> 
#define ull unsigned long long 

ull factorial(int n) { 
    ull fac = 1; 
    for (int i = 2; i <= n; i++) 
     fac *= i; 
    return fac; 
} 

std::vector<int> findPermutation(int len, long idx) { 
    std::vector<int> original = std::vector<int>(len); 
    std::vector<int> permutation = std::vector<int>(); 
    for (int i = 0; i < len; i++) { 
     original[i] = i; 
    } 

    ull currIdx = idx; 
    ull fac = factorial(len); 
    while (original.size() > 0) { 
     fac /= original.size(); 
     int next = (currIdx - 1)/fac; 
     permutation.push_back(original[next]); 
     original.erase(original.begin() + next); 
     currIdx -= fac * next; 
    } 
    return permutation; 
} 

Die findPermutation Funktion die Länge der ursprünglichen Zeichenfolge akzeptiert und der Index der erforderlichen Permutation und gibt ein Array zurück, das diese Permutation darstellt. Beispiel: [0, 1, 2, 3, 4] ist die erste Permutation einer beliebigen Zeichenfolge mit der Länge 5, und [4, 3, 2, 1, 0] ist die letzte (120.) Permutation.

Answer 2

Ich hatte ein ähnliches Problem haben, wo ich in einem Gtk TreeView viele Zeile zu speichern und wollen nicht alle von ihnen, dass ich durch die eine Reihe zugreifen möchten jedes Mal gehen, um Position und nicht durch seine Referenz.

Also, ich habe eine Karte der Positionen der Zeile erstellt, so dass ich sie leicht mit dem Parameter identifizieren konnte, den ich brauchte. Also, mein Vorschlag dazu ist, dass Sie alle Permutationen einmal durchlaufen und alle std::permutation in einem Array abbilden (ich habe einen std::vector), so können Sie darauf zugreifen, indem Sie myVector[permutation_id].

Hier ist meine Art, wie ich die Abbildung getan haben:

vector<int> FILECHOOSER_MAP; 
void updateFileChooserMap() { 
    vector<int> map; 
    TreeModel::Children children = getInterface().getFileChooserModel()->children(); 
    int i = 0; 
    for(TreeModel::Children::iterator iter = children.begin(); iter != children.end(); iter++) { 
     i++; 
     TreeModel::Row row = *iter; 
     int id = row[getInterface().getFileChooserColumns().id]; 
     if(id >= map.size()) { 
      for(int x = map.size(); x <= id; x++) { 
       map.push_back(-1); 
      } 
     } 
     map[id] = i; 
    } 
    FILECHOOSER_MAP = map; 
} 

Also in Ihrem Fall würden Sie nur über die Permutationen wie diese durchlaufen und Sie können sie in einer Art und Weise zuordnen, die Sie durch ihre ID accesing ihnen erlaubt .

Ich hoffe, das hilft Ihnen: D Grüßen, tagelicht