Encontrar un conjunto de permutaciones, con una restricción

Question

Tengo un conjunto de N^2 números y N bandejas. Se supone que cada contenedor tiene N números del conjunto asignado. El problema al que me enfrento es encontrar un conjunto de distribuciones que mapeen los números a los contenedores, satisfaciendo la restricción, que cada par de números puede compartir el mismo contenedor solo una vez.

Una distribución se puede representar con una matriz NxN, en la que cada fila representa un contenedor. Entonces, el problema es encontrar un conjunto de permutaciones de los elementos de la matriz, en los que cada par de números comparte la misma fila solo una vez. No importa qué fila sea, solo que dos números fueron asignados a la misma fila.

Ejemplo conjunto de 3 permutaciones que satisfacen la restricción para N = 8:

 
0 1 2 3 4 5 6 7 
8 9 10 11 12 13 14 15 
16 17 18 19 20 21 22 23 
24 25 26 27 28 29 30 31 
32 33 34 35 36 37 38 39 
40 41 42 43 44 45 46 47 
48 49 50 51 52 53 54 55 
56 57 58 59 60 61 62 63 

 
0 8 16 24 32 40 48 56 
1 9 17 25 33 41 49 57 
2 10 18 26 34 42 50 58 
3 11 19 27 35 43 51 59 
4 12 20 28 36 44 52 60 
5 13 21 29 37 45 53 61 
6 14 22 30 38 46 54 62 
7 15 23 31 39 47 55 63 

 
0 9 18 27 36 45 54 63 
1 10 19 28 37 46 55 56 
2 11 20 29 38 47 48 57 
3 12 21 30 39 40 49 58 
4 13 22 31 32 41 50 59 
5 14 23 24 33 42 51 60 
6 15 16 25 34 43 52 61 
7 8 17 26 35 44 53 62 

Una permutación que no pertenece en el conjunto de arriba:

 
0 10 20 30 32 42 52 62 
1 11 21 31 33 43 53 63 
2 12 22 24 34 44 54 56 
3 13 23 25 35 45 55 57 
4 14 16 26 36 46 48 58 
5 15 17 27 37 47 49 59 
6 8 18 28 38 40 50 60 
7 9 19 29 39 41 51 61 

Debido de múltiples colisiones con la segunda permutación, ya que, por ejemplo, ambos están emparejando los números 0 y 32 en una fila.

---

Enumerar tres es fácil, se compone de 1 permutación arbitraria, su transposición y una matriz en la que las filas están hechos de la matriz anterior' diagonales.

No puedo encontrar una forma de producir un conjunto que consista en más. Parece ser un problema muy complejo o un problema simple con una solución no evidente. De cualquier manera estaría agradecido si alguien tuviera alguna idea de cómo resolverlo en un tiempo razonable para el caso N = 8, o identifique el nombre académico adecuado del problema, para poder buscarlo en Google.

En caso de que se esté preguntando para qué sirve, estoy buscando un algoritmo de programación para un conmutador de barra transversal con 8 búferes, que sirve tráfico a 64 destinos. Esta parte del algoritmo de programación es independiente del tráfico de entrada, y cambia cíclicamente entre una serie de asignaciones de búfer de destino cableadas. El objetivo es que cada par de direcciones de destino compita por el mismo búfer solo una vez en el período de ciclo, y para maximizar la duración de ese período. En otras palabras, para que cada par de direcciones compitiera por el mismo búfer lo menos posible.

---

EDIT:

Aquí hay un código que tengo. CODE

Es codicioso, por lo general termina después de encontrar la tercera permutación. Pero debería existir un conjunto de al menos N permutaciones que satisfagan el problema.

La alternativa requeriría que elegir la permutación I implique buscar permutaciones (I + 1..N), para verificar si la permutación I es parte de la solución que consiste en el número máximo de permutaciones. Eso requeriría enumerar todas las permutaciones para verificar en cada paso, que es prohibitivamente costoso.

Answer 1

Lo lo que quiere es un combinatorial block design. Usando la nomenclatura en la página enlazada, quiere diseños de tamaño (n^2, n, 1) para k máximo. Esto le dará n (n + 1) permutaciones, usando su nomenclatura. Este es el máximo teórico posible mediante un argumento de conteo (ver la explicación en el artículo para la derivación de b de v, k y lambda). Dichos diseños existen para n = p^k para algunos primos p y enteros k, usando un plano afín. Se conjetura que los únicos planos afines que existen son de este tamaño. Por lo tanto, si puede seleccionar n, tal vez esta respuesta sea suficiente.

Sin embargo, si en lugar de la cantidad máxima teóricamente posible de permutaciones, solo desea encontrar un número grande (lo máximo que puede para un n^2 determinado), no estoy seguro de cómo se llama el estudio de estos objetos .

Answer 2

Haz una matriz de 64 x 64 x 8: bool forbidden [i] [j] [k] que indica si el par (i, j) ha aparecido en la fila k. Cada vez que use el par (i, j) en la fila k, establecerá el valor asociado en esta matriz en uno. Tenga en cuenta que solo usará la mitad de esta matriz para la que i < j.

Para construir una nueva permutación, comience probando el miembro 0, y verifique que al menos siete de [0] [j] [0] prohibidos estén desarmados. Si no quedan siete, incremente e intente de nuevo. Repita para completar el resto de la fila. Repita todo este proceso para llenar toda la permutación de NxN.

Probablemente hay optimizaciones que debería poder implementar a medida que implementa esto, pero esto debería funcionar bastante bien.

Answer 3

Posiblemente pueda reformular su problema en la teoría de grafos. Por ejemplo, comienza con el gráfico completo con N × N vértices. En cada paso, divide el gráfico en N N-cliques, y luego elimina todos los bordes utilizados.

Para este caso N = 8, K64 tiene 64 × 63/2 = 2,016 bordes, y sesenta y cuatro porciones de K8 tienen bordes 1792, por lo que su problema puede no sea imposible :-)

Answer 4

Correcto, el estilo codicioso no funciona porque se te acaban los números.

Es fácil ver que no puede haber más de 63 permutaciones antes de infringir la restricción. El día 64, tendrá que emparejar al menos uno de los números con otro con el que ya se haya emparejado. El principio del casillero.

De hecho, si usa la tabla de pares prohibidos que sugerí anteriormente, encontrará que hay un máximo de solo N + 1 = 9 permutaciones posibles antes de que se agote. La tabla tiene N^2 x (N^2-1)/2 = 2016 restricciones no redundantes, y cada nueva permutación creará N x (N elije 2) = 28 nuevas parejas. Entonces todos los emparejamientos se usarán después de 2016/28 = 9 permutaciones. Parece que darse cuenta de que hay tan pocas permutaciones es la clave para resolver el problema.

se puede generar una lista de N permutaciones numeradas n = 0 ... N-1 como

A_ij = (i * N + j + j * n * N) mod N^2 

que genera un nuevo permutación desplazando las columnas en cada permutación. La fila superior de la n-ésima permutación son las diagonales de la n-1ª permutación. EDITAR: Oops ... esto solo parece funcionar cuando N es primo.

Esta pierde una última permutación, que se puede obtener mediante la transposición de la matriz:

A_ij = j * N + i