Auflistung aller Permutationen einer gegebenen Menge von Werten

Question

Ich interessiere mich für Vergleiche verschiedener Techniken/Ansätze, die man benutzen könnte, um alle möglichen Permutationen einer gegebenen Menge zu erzeugen.

Answer 1

Sie können zwischen Leistung, besonderer Verteilung und Einfachheit wählen. Mit einer bestimmten Verteilung meine ich, ob Sie eine bestimmte Reihenfolge, wie lexikographisch, der Ausgabe interessieren.

Der am besten funktionierende Algorithmus meines Wissens ist der Steinhaus algorithm. Es ist optimal bis zu einer multiplikativen Konstante in dem Sinne, dass nur eine konstante Anzahl von Prozessoranweisungen notwendig ist, um eine Permutation zu erzeugen (nicht die zum Ausgeben notwendigen Anweisungen zu zählen, die nicht immer benötigt werden).

Es gibt auch einen sehr einfachen Algorithmus, der die Permutationen in der lexikographischen Ordnung erzeugt, die Sie wahrscheinlich als rekursive Prozedur selbst neu erfinden können, und deren Leistung O (n.log (n) .log (n)), also ungefähr das gleiche wie das Erstellen der Liste mit einer anderen Methode und Sortieren.

bearbeiten: hier ist Pseudo-Code des einfachen Algorithmus:

void permute(Element[] permutationPrefix, Set rest) 
{ 
    if (rest.IsEmpty) { 
     // permutationPrefix is now a full permutation 
     print(permutationPrefix); 
    } else { 
     foreach (element in rest) { 
      permutationPrefix.Append(element); 
      permute(permutationPrefix, rest.Minus(element)) 
      permutationPrefix.Length--; // cut away the last item 
     } 
    } 
} 

Zunächst nennen dies mit einem leeren permutationPrefix und rest den vollen Satz zu halten; Wenn diese Menge eine sortierte Datenstruktur ist, werden die Permutationen in lexikographischer Reihenfolge ausgegeben.

Beachten Sie, dass wir den Satz bei jedem rekursiven Aufruf kopieren und ändern, was die teuerste Operation des gesamten Algorithmus ist, möglicherweise zusammen mit der print-Methode. Die Kosten einer einzelnen Satzkopie sind logarithmisch in der Gesamtzahl der Permutationen n; und da die Tiefe des rekursiven Aufrufstapels ebenfalls logarithmisch ist, folgt die Leistungsschätzung O (n.log (n) .log (n)).

(Dieser Algorithmus ist auch für die Umwandlung in ein gut erzogener zufällige Permutation Generator geeignet.)

Answer 2

Diese Frage bereits gestellt hat und beantwortet (oft in der Tat):

Algorithm to generate all possible permutations of a list?

Permutations with a given integer

Persönlich denke ich, dass der Steinhaus-Algorithmus das Problem überdenkt: es ist nicht viel schneller als die naivste Implementierung.

Java-ähnlichen Pseudocode der naiven Umsetzung:

List<List<Element>> generateAllPermutations(List<Element> input) 
{ 
    List<Element> output = new ArrayList<Element>(); 
    if (input.size() == 0) 
     return output; 
    for (Element first : input) { 
     for (List<Element> sequence : generateAllPermutations(input - first)) 
      output.add(first + sequence); 
    } 
}