Algoritmo di arrangiamento efficiente in java

Sto provando a scrivere un metodo che calcoli tutte le permutazioni di un gruppo elettrogeno in cui l'ordine è importante. Credo che questi siano chiamati "accordi". Quello che voglio dire con questo è:Algoritmo di arrangiamento efficiente 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}, {}}

ecc La mia impressione è che, dato un insieme S, dovrei generare ogni permutazione di ogni sottoinsieme della Powerset di S. Quindi, prima di generare il Powerset, poi mappare una permutazione funzione su ogni set.

Il problema è che questo è immensamente complesso - qualcosa come O (Σn!/K!) Con k = 0..n.

Mi chiedo se esistono algoritmi esistenti che facciano questo genere di cose in modo molto efficiente (forse un'implementazione parallela). O forse anche se esiste un algoritmo parallelo di powerset e esiste un algoritmo di permutazione parallelo, posso combinare i due.

Pensieri?

fonte

2012-06-18 rhombidodecahedron

Forse controlla questo post: http://stackoverflow.com/questions/1506078 – squiguy

possibile duplicato di [Fast permutation -> number -> algoritmi di permutazione mapping] (http://stackoverflow.com/questions/1506078/fast -permutation-number-permutation-mapping-algorithms) – Makoto

Non penso che sia un duplicato. Ho letto quella discussione e mi chiede qualcosa di molto diverso. Le soluzioni sono in qualche modo simili nel tema, ma sono certamente abbastanza diverse da giustificare thread separati. – rhombidodecahedron

La libreria guava fornita da google contiene diversi metodi per permutare le raccolte.

Vedere javadoc della classe com.google.common.collect.Collections2 here.

fonte

2012-06-19 15:31:03 luchoct

Buona risposta, molto utile per le piccole collezioni, ma non credo che l'implementazione si riduca quando N cresce. –

Per fare ciò si generano prima le combinazioni per gli slot 1-n dove n è il numero di elementi nel gruppo di potenza. Ad esempio, se si dispone di 3 elementi, allora si avrà:

C (3, 3) = 1 combinazione (abc)
C (3, 2) = 3 combinazioni (ab) (ac) (bc)
C (3, 1) = 3 combinazioni (a) (b) (c)

Ora, si generano le permutazioni per ogni combinazione.

Esistono algoritmi noti per calcolare permutazioni e combinazioni. Ad esempio, "The Art of Computer Programming" di Knuth, volume 4A, sezioni 7.2.1.2 e 7.2.1.3, spiega esattamente come costruire gli algoritmi rilevanti.

fonte

2012-09-20 22:34:14

Algoritmo di arrangiamento efficiente in java

risposta

Problemi correlati