Algoritmo de arreglo eficiente en Java

set permutation

Question

Estoy tratando de escribir un método que calculará todas las permutaciones de un conjunto de potencia donde el orden importa. Creo que estos se llaman "arreglos". Lo que quiero decir con esto es:

{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}, {}}

etc. Mi impresión es que, dado un conjunto S, debería generar cada permutación de cada subconjunto del conjunto de potencias de S. Entonces, primero genere el conjunto de potencias, luego asigne una función de permutación a cada conjunto.

El problema es que esto es inmensamente complejo, algo así como O (Σn! / K!) Con k = 0..n.

Me pregunto si hay algún algoritmo existente que haga este tipo de cosas de manera muy eficiente (quizás una implementación paralela). O quizás, incluso si existe un algoritmo paralelo de powerset y existe un algoritmo de permutación paralelo, puedo combinar los dos.

¿Pensamientos?

Answer 1

La biblioteca de guayaba proporcionada por google contiene diferentes métodos para permutar colecciones.

Vea el javadoc de la clase com.google.common.collect.Collections2 aquí .

Answer 2

Para hacer esto, primero genera las combinaciones para ranuras 1-n donde n es la cantidad de elementos en el conjunto de potencia. Por ejemplo, si tiene 3 elementos, tendrá:

C (3, 3) = 1 combinación (abc)
C (3, 2) = 3 combinaciones (ab) (ac) (bc)
C (3, 1) = 3 combinaciones (a) (b) (c)

Ahora, generas las permutaciones para cada combinación.

Existen algoritmos bien conocidos para calcular permutaciones y combinaciones. Por ejemplo, Knuth''s "The Art of Computer Programming", volumen 4A, Secciones 7.2.1.2 y 7.2.1.3, explican exactamente cómo construir los algoritmos relevantes.