¿Existe un algoritmo para generar todas las permutaciones circulares únicas de un conjunto múltiple?

Question

me encontré con este problema al hacer un poco de programación entusiasta. El problema se puede expresar como sigue:

  

Para un Un conjunto múltiple, sea P (A) denota el   conjunto de todas las permutaciones posibles de A.   P (A) se divide naturalmente en   subconjuntos disjuntos que son la equivalencia   clases, con la relación de equivalencia   siendo "puede estar relacionado por desplazamientos circulares." enumerar todas   estas clases de equivalencia mediante la generación de   exactamente un miembro de cada uno de ellos.

Por ejemplo, considere la multiset {0, 1, 1, 2}. Las permutaciones "0112" y "1201" son permutaciones únicas, pero este último se pueden encontrar por-circular el desplazamiento de la primera y viceversa. El algoritmo deseado no debe generar ambos.

Por supuesto, un enfoque de fuerza bruta es posible: basta con generar permutaciones - independientemente de la duplicación circular - el uso de cualquiera de los algoritmos de permutación multiconjuntos y duplicaciones de descarte encontraron en comparación con los resultados anteriores. Sin embargo, esto tiende a ser ineficaz en la práctica. El algoritmo deseado debe requerir un mínimo, si no es cero contabilidad.

Cualquier penetraciones en este problema es muy apreciada.

Answer 1

Sawada es el algoritmo

Answer 2

Es un poco más fácil para ir a esto abajo:

si A sólo contiene 1 elemento, P (A) también contiene una permutación. Es fácil ver por las mismas obras si A sólo contiene 2 elementos.

Ahora, vamos a suponer que ya tiene todo P (A) de A con n elementos, y añadir un elemento. que puede ir en cualquiera de n puntos en cualquiera de las permutaciones en P (A).

Creo que esta idea se traduce bastante directamente a un algoritmo recursivo en el idioma de su elección, y espero que mi explicación era lo suficientemente claro.

EDIT: Sé que tipo de ignorado el hecho de que A puede contener elementos duplicados, pero sigue pensando en esa parte:)

Al igual que un embargo - si ordenado de A antes de iniciar el algoritmo de permutación, creo que esto podría eliminar duplicados. (Sigue pensando en eso también)

Answer 3

Para una comprensión intuitiva del problema creo que podemos emplear esta metáfora. Visualizar un reloj en la pared, pero en lugar de tener 12 posiciones en la cara que tiene n donde n es el número de elementos en su conjunto.

A continuación, la clase cada equivalencia es sólo una asignación de un elemento de A a una posición en la esfera del reloj.

Una vez asignado otra permutación de la misma clase de equivalencia puede ser generado por una simple rotación del reloj de la pared.

Para generar otra permutación sin relación de A es necesario tener un elemento saltar sobre al menos un otro elemento.

Ahora el algoritmo tal como la veo sería comenzar con una asignación, por ejemplo, decir que tuvimos cuatro elementos en A = {a, b, c, d} y que ellos asignado a las 12, 3, 6 y 9 posiciones respectivamente para mayor claridad visual. Entonces nuestra primera operación sería de intercambio a y b. entonces A y C, a continuación, A y D, entonces podríamos ir a B y de intercambio con el elemento en la posición 3 que ahora es c.

Hacer esto hasta que llegamos d generaría un representante de todas las clases de equivalencia.

Esto no toma el cuidado de los duplicados, pero debería ser mucho más eficiente que la generación de todas las permutaciones de A.

Answer 4

El pensamiento que viene a la mente es que para cualquier conjunto que tiene al menos un elemento que sólo aparece una vez y luego se puede poner ese elemento en la primera posición de su lista de todas las respuestas y luego generar todas las permutaciones del resto de los números. Esta es una solución bastante trivial, ya que el hecho de que su primer elemento es único asegura que no hay equivalentes por ciclo de desplazamiento de los elementos. Es evidente, entonces todas las soluciones que generan deben ser únicos.

El problema obvio es que si no tiene elementos que son sencillos entonces se rompe por completo. La razón principal por la que pongo esto en es robaba hay varias otras soluciones que se ocupan de no duplicados y creo que éste es más eficaz que ellos (Resuelve más casos) por lo que es digno de mención. También es bastante simple en términos de entender cómo funciona y su aplicación. Sólo espero que mi razonamiento es sólido. ; -)

Editar para más pensamientos:

Se me ocurre que este principio se puede extender a la situación en la que usted tiene duplicados en cierta medida.

Si se toma un elemento (que asumimos ahora se repite) se puede ver en tan sólo sus permutaciones y cuáles permitiría la repetición de cambio de ciclo, como antes assumign que pueda un "bloqueo" en su lugar sin pérdida de generalidad. por ejemplo, si tiene un total de 6 elementos y A aparece dos veces en este conjunto, entonces puede tener:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

El último de estos es la misma que la primera (a menos de desplazamiento cíclico) por lo que puede ser ignorada, ídem el segundo y cuarto. La tercera (AXXAXX) puede ser completado un ciclo por tres para volver a sí mismo por lo que tiene el potencial de ciclos. Los dos primeros nunca puede dar lugar a ciclos no importa cuántas veces uses el ciclo de ellas por lo que sin embargo distribuir los elementos restantes sólo se necesitan asegurarse de que son distribuciones únicas y que están garantizados para conseguir resultados únicos por ciclo.

En el tercer ciclo de patrón que lata (AXXAXX) que tendría que mirar en el elemento B y repita el proceso para aquellos. Esta vez desafortunadamente que sería incapaz de utilizar el truco de bloquear el primer valor para ahorrar tiempo.

No estoy 100% seguro de cómo va a ir sobre la fabricación de esto en un programa totalmente funcional, pero algunos de sus thougths sobre cómo evitar tener que fuerza bruta.

Answer 5

propongo aquí una solución implementada en Python

import itertools as it

L = ['a','b','c','d']
B = it.combinations(L,2)
swaplist = [e for e in B]
print 'List of elements to permute:' 
print swaplist
print
unique_necklaces = []
unique_necklaces.append(L)
for pair in swaplist:
    necklace = list(L)
    e1 = pair[0]
    e2 = pair[1]
    indexe1 = L.index(e1)
    indexe2 = L.index(e2)
    #swap
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1]
    unique_necklaces.append(necklace)

for n in unique_necklaces:
    # Commented code display the rotation of the elements in each necklace
    print 'Necklaces'
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)]   

La idea es construir diferentes collares por permutaciones de dos elementos. Para una lista de cuatro elementos a, b, c, d el algo rendimientos:

['a', 'b', 'c', 'd']
['b', 'a', 'c', 'd']
['c', 'b', 'a', 'd']
['d', 'b', 'c', 'a']
['a', 'c', 'b', 'd']
['a', 'd', 'c', 'b']
['a', 'b', 'd', 'c']