Algorithmus zum Generieren aller Permutationen unterschiedlicher Größen einer Gruppe von ganzen Zahlen?

Question

Nehmen wir an, ich habe ein Array von ganzen Zahlen, zum Beispiel [3,4,2,7,8,5]

Wie würde ich unterschiedlich große Permutationen von diesem Array generieren?

Wie erhalten alle möglichen Paare von 2 oder alle möglichen Sätze von 3? von 4?

Ich würde gerne in der Lage sein, dies sehr schnell zu tun.

Answer 1

Für einen sprachunabhängigen Ansatz aus den ersten Prinzipien: Aufzählung aller Teilmengen der Größe k (für k = 2, ..., n, wobei n die Größe des Arrays ist). Der Wikipedia-Artikel über Kombinationen hat einen Abschnitt über ihre enumeration. Verwenden Sie für jede aufgelistete Teilmenge die Johnson-Trotter algorithm für die Aufzählung der Permutationen davon. Die Gesamtzahl solcher Permutationen wird sehr schnell sehr groß. Zum Beispiel, mit nur 10 Artikeln gibt es 9.864.090

Viele Sprachen werden Bibliotheksunterstützung haben. Zum Beispiel ist es eine einfache Programmierübung in Python (mit seinem itertools Modul). Hier ist ein Generator zur Herstellung solcher Permutationen:

import itertools 

def allPermutations(items): 
    n = len(items) 
    for k in range(2,n+1): 
     for combo in itertools.combinations(items,k): 
      for perm in itertools.permutations(combo): 
       yield perm 

Zum Beispiel wertet list(allPermutations([3,4,2,7,8,5])) in die Liste aller 1950 solcher Permutationen von [3,4,2,7,8,5] gezogen.

Answer 2

Sie können einen beliebigen Algorithmus (wie bekannt Narayana algorithm) verwenden, um alle Permutationen der Größe N zu generieren.

Wenn nun in dieser Gesamtsequenz von Permutationen betrachten Sie nur Permutationen mit Präfix (a , ein , ..., a _k), wo ein < ein < ... < a _k, dann bilden die Schwanzabschnitte aller solcher Permutationen eine Abfolge aller möglichen Permutationen der Länge N - k.

Auf diese Weise können Sie alle Permutationen der Länge N und kürzer mit einem einzigen Durchlauf durch alle Permutationen der Länge N generieren.

Hier ist, was eine C++ Implementierung wie

#include <iostream> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    int a[] = { 2, 3, 4, 5, 7, 8 }; 

    do 
    { 
    for (auto ite = std::begin(a); ite != std::end(a); ++ite) 
     if (std::is_sorted(std::begin(a), ite)) 
     { 
     std::copy(ite, std::end(a), std::ostream_iterator<int>(std::cout)); 
     std::cout << std::endl; 
     } 

    } while (std::next_permutation(std::begin(a), std::end(a))); 
} 

da aufeinanderfolgende Aufrufe von std::is_sorted (ich nahm sich die Freiheit von Vorsortierung Ihre Eingabe festgelegt.) Innerhalb des oben ist natürlich nicht optimal, aussehen könnte Der Zyklus for wiederholt wiederholt, was bereits in der vorherigen Iteration überprüft wurde. Aber auch hier soll diese Implementierung nur illustrativen Zwecken dienen.

Jetzt ist die Frage, ob Sie mit der Reihenfolge zufrieden sind, in der diese Permutationen generiert werden. Der obige Ansatz gruppiert sie nicht nach Länge.

---

Alternativ können Sie durch all possible combinations, iterieren und dann erzeugen nur alle möglichen Permutationen für jede Kombination.