repeticion recursividad recursiva permutaciones permutacion numeros combinaciones caracteres algoritmo c++ c arrays algorithm permutation

c++ - recursividad - Algoritmo para encontrar el conjunto isomorfo de permutaciones.



permutacion recursiva c++ (5)

Hay una solución muy simple para esto: la transposición.

Si dos conjuntos son isomorfos, significa que existe una asignación uno a uno, donde el conjunto de todos los números en el índice i en el conjunto S1 es igual al conjunto de todos los números en algún índice k en el conjunto S2 . Mi conjetura es que no hay dos conjuntos no isomorfos que tengan esta propiedad.

(1) Ejemplo de Jean Logeart:

0: [[1,2,3],[3,2,1]] 1: [[2,3,1],[1,3,2]] 2: [[1,2,3],[2,3,1]] 3: [[3,2,1],[1,2,3]] Perform ONE pass: Transpose, O(n): 0: [[1,3],[2,2],[3,1]] Sort both in and between groups, O(something log something): 0: [[1,3],[1,3],[2,2]] Hash: "131322" -> 0 ... "121233" -> 1 "121323" -> 2 "131322" -> already hashed. 0 and 3 are isomorphic.

(2) el contraejemplo de vsoftco en su comentario a la respuesta de Jean Logeart:

A = [ [0, 1, 2], [2, 0, 1] ] B = [ [1, 0, 2], [0, 2, 1] ] "010212" -> A "010212" -> already hashed. A and B are isomorphic.

Puede convertir cada conjunto en una secuencia ordenada transpuesta o hash o cualquier objeto comprimido para la comparación de tiempo lineal. Tenga en cuenta que este algoritmo considera los tres conjuntos A , B y C como isomorfos, incluso si uno p convierte A en B y otro p convierte A en C Claramente, en este caso, hay p s para convertir cualquiera de estos tres conjuntos al otro, ya que todo lo que estamos haciendo es mover cada i en un conjunto a un k específico en el otro. Si, como dijo, su objetivo es "eliminar las permutaciones isomorfas", todavía obtendrá una lista de conjuntos para eliminar.

Explicación:

Supongamos que, junto con nuestro hash ordenado, mantuvimos un registro de las permutaciones de cada una de las cuales procedí. Contra-ejemplo de vsoftco:

010212 // hash for A and B 100110 // origin permutation, set A 100110 // origin permutation, set B

Para confirmar el isomorfismo, debemos mostrar que las i agrupan en cada índice desde el primer conjunto movido a un índice en el segundo conjunto, cuyo índice no importa. La clasificación de los grupos de i no invalida la solución, sino que sirve para confirmar el movimiento / permutación entre conjuntos.

Ahora, por definición, cada número en un hash y cada número en cada grupo en el hash se representa en una permutación de origen exactamente una vez para cada conjunto. Sin embargo, elegimos organizar los números en cada grupo de i en el hash, tenemos la garantía de que cada número en ese grupo representa una permutación diferente en el conjunto; y en el momento en que asignamos teóricamente ese número, tenemos la garantía de que está "reservado" solo para esa permutación e índice. Para un número dado, digamos 2 , en los dos hashes, tenemos la garantía de que proviene de un índice y permutación en el conjunto A , y en el segundo hash corresponde a un índice y permutación en el conjunto B Eso es todo lo que realmente necesitamos mostrar: que el número en un índice para cada permutación en un conjunto (un grupo de i distintos) fue a un índice solo en el otro conjunto (un grupo de k distintos). A qué permutación e índice al que pertenece el número es irrelevante.

Recuerde que cualquier conjunto S2 , isomorfo para establecer S1 , puede derivarse de S1 usando una función de permutación o varias combinaciones de diferentes funciones de permutación aplicadas a los miembros de S1 . Lo que realmente representa la ordenación o reordenación de nuestros números y grupos es la permutación que estamos eligiendo asignar como la solución al isomorfismo en lugar de una asignación real de qué número provino de qué índice y permutación. Aquí está nuevamente el contraejemplo de vsoftco, esta vez agregaremos los índices de origen de nuestros hashes:

110022 // origin index set A 001122 // origin index set B

Por lo tanto nuestra permutation , una solución al isomorfismo, es:

O, en orden:

(Observe que en el ejemplo de Jean Logeart hay más de una solución para el isomorfismo).

Tengo un conjunto de permutaciones, y quiero eliminar las permutaciones isomorfas.

Tenemos S conjuntos de permutaciones, donde cada conjunto contiene K permutaciones, y cada permutación se representa como una matriz de N elementos. Actualmente lo estoy guardando como una matriz int pset[S][K][N] , donde S , K y N son fijos, y N es más grande que K.

Dos conjuntos de permutaciones, A y B , son isomorfos , si existe una permutación P , que convierte elementos de A a B (por ejemplo, si a es un elemento del conjunto A , entonces P(a) es un elemento del conjunto B ). En este caso podemos decir que P hace que A y B isomorfos .

Mi algoritmo actual es:

  1. Elegimos todos los pares s1 = pset[i] y s2 = pset[j] , de modo que i < j
  2. Cada elemento de los conjuntos elegidos ( s1 y s2 ) están numerados de 1 a K Eso significa que cada elemento se puede representar como s1[i] o s2[i] , donde 0 < i < K+1
  3. Para cada permutación T de K elementos, hacemos lo siguiente:
    • Encuentre la permutación R , tal que R(s1[1]) = s2[1]
    • Verifique si R es una permutación que hace que s1 y T(s2) isomórficos, donde T(s2) es un reordenamiento de los elementos (permutaciones) del conjunto s2 , así que básicamente solo verificamos si R(s1[i]) = s2[T[i]] , donde 0 < i < K+1
    • Si no, pasamos a la siguiente permutación T

Este algoritmo funciona realmente lento: O(S^2) para el primer paso, O(K!) Para recorrer cada permutación T , O(N^2) para encontrar la R y O(K*N) para verificar si La R es la permutación que hace que s1 y s2 isomorfas, por lo que es O(S^2 * K! * N^2) .

Pregunta: ¿Podemos hacerlo más rápido?

Para verificar si dos conjuntos S₁ y S₂ son isomorfos, puede hacer una búsqueda mucho más corta.

Si son isomorfos, entonces hay una permutación t que mapea cada elemento de S₁ a un elemento de S₂ ; para encontrar t puede simplemente seleccionar cualquier elemento fijo p de S₁ y considerar las permutaciones

t₁ = (1/p) q₁ t₂ = (1/p) q₂ t₃ = (1/p) q₃ ...

Para todos los elementos q de S₂ . Para, si existe una t válida, debe asignar el elemento p a un elemento de S₂ , por lo que solo las permutaciones que mapean p a un elemento de S₂ son posibles candidatos.

Además, dado un candidato t para verificar si dos conjuntos de permutaciones S₁t y S₂ son iguales, se podría usar un hash computado como x-o de un código hash para cada elemento, haciendo el chequeo completo de todas las permutaciones solo si el hash coincide.

Puedes ordenar y comparar:

// 1 - sort each set of permutation for i = 0 to S-1 sort(pset[i]) // 2 - sort the array of permutations itself sort(pset) // 3 - compare for i = 1 to S-1 { if(areEqual(pset[i], pset[i-1])) // pset[i] and pset[i-1] are isomorphic }

Un ejemplo concreto:

0: [[1,2,3],[3,2,1]] 1: [[2,3,1],[1,3,2]] 2: [[1,2,3],[2,3,1]] 3: [[3,2,1],[1,2,3]]

Después del 1:

0: [[1,2,3],[3,2,1]] 1: [[1,3,2],[2,3,1]] // order changed 2: [[1,2,3],[2,3,1]] 3: [[1,2,3],[3,2,1]] // order changed

Después del 2:

2: [[1,2,3],[2,3,1]] 0: [[1,2,3],[3,2,1]] 3: [[1,2,3],[3,2,1]] 1: [[1,3,2],[2,3,1]]

Después del 3:

(2, 0) not isomorphic (0, 3) isomorphic (3, 1) not isomorphic

¿Qué pasa con la complejidad?

  • 1 es O(S * (K * N) * log(K * N))
  • 2 es O(S * K * N * log(S * K * N))
  • 3 es O(S * K * N)

Por lo tanto, la complejidad global es O(S * K * N log(S * K * N))

Supongamos que dos elementos de s1, s2 / en S son isomorfos. Luego, si p1 y p2 son permutaciones, entonces s1 es isomorfo a s2 si p1 (s1) es isomorfo a p2 (s2) donde pi (si) es el conjunto de permutaciones obtenidas al aplicar pi a cada elemento en si .

Para cada i en 1 ... sy j en 1 ... k , elija el miembro j de th y encuentre la permutación que lo cambie a la unidad. Aplícalo a todos los elementos de si . Hash cada una de las k permutaciones a un número, obteniendo k números, para cualquier elección de i y j , al costo nk .

Comparando los conjuntos de hash para dos valores diferentes de i y j es k ^ 2 <nk . Por lo tanto, puede encontrar el conjunto de coincidencias candidatas al costo s ^ 2 k ^ 3 n . Si el número real de coincidencias es bajo, la complejidad general está muy por debajo de lo que especificó en su pregunta.

Tome a0 en A Luego encuentre que es inverso (rápido, O(N) ), a0inv . Luego elija algo de i en B y defina P_i = b_i * ainv y verifique que P_i * a genere B , al variar a sobre A Haga esto para cada i en B. Si no encuentra ninguna i para la cual se mantiene la relación, entonces los conjuntos no son isomorfos. Si encuentras tal i , entonces los conjuntos son isomorfos. El tiempo de ejecución es O(K^2) para cada par de conjuntos que verifica, y necesitaría verificar O(S^2) para que termine con O(S^2 * K^2 * N) .

PD: asumí aquí que con " mapas A a B " quiere decir mapear bajo la composición de permutación, entonces P(a) es en realidad la permutación P compuesta con la permutación a , y he usado el hecho de que si P es una permutación, entonces debe existir una i para la cual Pa = b_i para algunas a .

EDITAR Decidí recuperar mi respuesta ya que no estoy convencido de que la anterior (@Jean Logeart) basada en la búsqueda sea correcta. Si es así, con gusto eliminaré el mío, ya que su desempeño es peor, pero creo que tengo un contraejemplo, vea los comentarios debajo de la respuesta de Jean.