algoritmo de disposición eficiente en java

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:algoritmo de disposición eficiente en 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}, {}}

etc. Mi impresión es que, dado un conjunto S, que debería generar todas las combinaciones de cada subconjunto de la powerset de S. Así que primero generar el powerset, a continuación, asignar una permutación función en cada conjunto.

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

Me pregunto si hay algoritmos existentes que hacen este tipo de cosas de manera muy eficiente (tal vez 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?

Fuente

2012-06-18 rhombidodecahedron

Tal vez, consulte esta publicación: http://stackoverflow.com/questions/1506078 – squiguy

posible duplicado de [Permutación rápida -> número -> algoritmos de asignación de permutación] (http://stackoverflow.com/questions/1506078/fast) -permutation-number-permutation-mapping-algorithms) – Makoto

No creo que sea un duplicado. Leo ese hilo y pide algo bastante diferente. Las soluciones son algo similares en el tema pero son ciertamente lo suficientemente diferentes como para garantizar hilos separados. – rhombidodecahedron

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

Consulte el javadoc de la clase com.google.common.collect.Collections2 here.

Fuente

2012-06-19 15:31:03 luchoct

Buena respuesta, muy útil para colecciones pequeñas, pero no creo que la implementación se amplíe cuando N crece. –

Para hacer esto primero se generan las combinaciones para ranuras 1-n donde n es el número de elementos en el conjunto de potencia. Por ejemplo, si tiene 3 elementos, entonces tendrá que:

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

Ahora, que generan 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.

Fuente

2012-09-20 22:34:14

algoritmo de disposición eficiente en java

Respuesta

Cuestiones relacionadas