Encontrar todas las permutaciones que coinciden con un conjunto de reglas

Me dan N números y para ellos aplican M reglas sobre su orden. Las reglas se representan en un par de índices y cada par (A, B) indica que el número con índice A (número A) debe ser DESPUÉS del número B-ésimo, no tiene que estar al lado de él. .Encontrar todas las permutaciones que coinciden con un conjunto de reglas

Ex: N = 4 
    1 2 3 4 
    M = 2 
    3 2 
    3 1 

Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:)

El algoritmo debe darme todas las permutaciones disponibles que no se rompen las reglas, al igual que en el ejemplo - 3 deben estar siempre después de 2 y después 1.

Probé fuerza bruta sino que dejase' t trabajo (aunque la fuerza bruta debería funcionar aquí, N está en el rango (1,8).)

¿Alguna idea?

Fuente

2010-02-27 VaioIsBorn

¿Podría explicar cómo los números N entran en esto? ¿Cuál sería la respuesta si las N son {1, 2, 3, 4}? –

Por lo que puedo ver, los N números que le dan son irrelevantes para la pregunta que está haciendo. ¿Es esto correcto? – sykora

N es la cantidad de números que hay, en este caso N = 4 porque hay cuatro números, 1..4. – VaioIsBorn

Solo como sugerencia.

Puede tratar su conjunto de reglas como un gráfico. Cada índice es un vértice, cada regla es un borde dirigido.

Cualquier orden apropiado de los números (es decir, una permutación que satisface las normas) corresponde al así llamado topological ordering de la gráfica anterior. Para generar todos los pedidos válidos de sus números, debe generar todos los ordenamientos topológicos posibles de ese gráfico.

P.S. El primer algoritmo para ordenamiento topológico dado en la página enlazada de Wikipedia ya permite una solución bastante sencilla que enumeraría todas las permutaciones válidas. Tomará un poco de esfuerzo y algo de cuidado implementar, pero no es ciencia espacial.

Fuente

2010-02-27 00:44:59 AnT

Como un paso antes de ir a un tipo topológico completo, al menos puede crear fragmentos ordenados para simplificar la fuerza bruta. Por ejemplo, si las reglas de prioridad son: 3,4 4,5 5,8 Usted sabe que puede permutar [3458] con antepone, insertos y anexa de sus números enteros no restringidos por las reglas de prioridad (esto generaliza del curso en el anterior) –

El forzamiento bruto sería going through every permutation, que es O (N!), Y para cada permutación simplemente recorre todas las reglas para confirmar que aplpi, que es O (M). Esto termina en O (N! M) que es un poco ridículo, pero no debería "no funcionar" para un conjunto tan pequeño.

Fuente

2010-02-27 00:49:08 Tanzelax

en realidad él podía verificar las reglas, mientras creaba permutaciones. Esto reduciría considerablemente el tiempo y terminaría con un resultado. – Kugel

Estoy de acuerdo. Si N = 8 es el más alto que necesita para poder manejarlo, entonces probablemente no valga la pena su tiempo para encontrar algo mejor que la fuerza bruta para algo como esto. –

Sí, definitivamente hay muchas optimizaciones fáciles de realizar en una solución de fuerza bruta, pero menciona que tiene problemas incluso con eso. – Tanzelax

Honestamente, su mejor opción es volver y conseguir que la solución de fuerza bruta funcione. Una vez hecho esto (y si todavía tiene tiempo, etc.) puede buscar un mejor algoritmo.

EDIT para el votante de abajo. El estudiante debe (debe) intentar hacer los deberes a tiempo. Por lo que parece, su tarea es un ejercicio de programación donde una solución de fuerza bruta sería adecuada. Ayudarlo a descubrir un algoritmo eficiente no está abordando su problema REAL.

En este caso, ha intentado con el enfoque de la fuerza bruta simple (que todo el mundo acepta debe funcionar para valores pequeños de N) y lo abandonó prematuramente para intentar algo que probablemente sea más difícil. Cualquier desarrollador experimentado le dirá que esta es una mala idea. El estudiante necesita y merece que se lo digan, y si es sensato, prestará atención. Pero, obviamente, es su elección ...

Fuente

2010-02-27 01:14:03

@serial_downvoter: cancelado. ¡Jaja! –

Encontrar todas las permutaciones que coinciden con un conjunto de reglas

Respuesta

Cuestiones relacionadas