Effiziente Anordnung Algorithmus in Java

Ich versuche, eine Methode zu schreiben, die alle Permutationen eines Power-Sets berechnet, wo Reihenfolge wichtig ist. Ich glaube, das nennt man "Arrangements". Was ich damit meine, ist:Effiziente Anordnung Algorithmus in Java

{a} -> {{a}, {}} 
{a,b} -> {{a,b}, {b,a}, {a}, {b}, {}} 
{a,b,c} -> {{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}, {a,b}, {a,c}, {b,a}, {b,c}, {c,a}, {c,b}, {a}, {b}, {c}, {}}

usw. Mein Eindruck ist, dass ein Satz S gegeben, ich sollte also zuerst die Powerset erzeugen, dann Karte eine Permutation jede Permutation von jeder Teilmenge der Potenz von S. erzeugen Funktion auf jeden Satz.

Das Problem ist, dass dies immens komplex ist - etwas wie O (Σn!/K!) Mit k = 0..n.

Ich frage mich, ob es irgendwelche vorhandenen Algorithmen gibt, die diese Art von Sache sehr effizient tun (vielleicht eine parallele Implementierung). Oder vielleicht sogar, wenn ein Parallel-Powerset-Algorithmus existiert und ein paralleler Permutationsalgorithmus existiert, kann ich die beiden kombinieren.

Gedanken?

Quelle

2012-06-18 rhombidodecahedron

Vielleicht überprüfen Sie diesen Beitrag aus: http://StackOverflow.com/Questions/1506078 – squiguy

mögliche Duplikate von [Schnelle Permutation -> Anzahl -> Permutation Mapping-Algorithmen] (http://StackOverflow.com/Questions/1506078/Fast -Permutation-Nummer-Permutation-Mapping-Algorithmen) – Makoto

Ich glaube nicht, dass es ein Duplikat ist. Ich lese diesen Thread und es fragt nach etwas ganz anderem. Die Lösungen sind im Thema etwas ähnlich, aber sind sicherlich unterschiedlich genug, um separate Threads zu gewährleisten. – rhombidodecahedron

Die von Google bereitgestellte Guava-Bibliothek enthält verschiedene Methoden zum Permutieren von Sammlungen.

Siehe das Javadoc der Klasse com.google.common.collect.Collections2 here.

Quelle

2012-06-19 15:31:03 luchoct

Gute Antwort, wirklich praktisch für kleine Sammlungen, aber ich glaube nicht, dass die Implementierung skaliert, wenn N wächst. –

Dazu generieren Sie zuerst die Kombinationen für 1-n Steckplätze, wobei n die Anzahl der Elemente in der Leistungsgruppe ist. wenn Sie 3 Elemente zum Beispiel haben, dann haben Sie:

C (3, 3) = 1 Kombination (abc)
C (3, 2) = 3 Kombinationen (ab) (ac) (bc)
C (3, 1) = 3-Kombinationen (a) (b) (c)

Nun, um die Permutationen für jede Kombination zu erzeugen.

Es gibt wohlbekannte Algorithmen zum Berechnen von Permutationen und Kombinationen. Zum Beispiel erklärt Knuths "Die Kunst der Computerprogrammierung", Band 4A, Abschnitte 7.2.1.2 und 7.2.1.3, genau, wie man die relevanten Algorithmen konstruiert.

Quelle

2012-09-20 22:34:14

Effiziente Anordnung Algorithmus in Java

Antwort

Verwandte Themen