Encontrar un conjunto de permutaciones, con una restricción

Question

Tengo un conjunto de N ^ 2 números y N bins. Cada contenedor se supone que tiene N números del conjunto asignado a la misma. El problema que estoy enfrentando es encontrar un conjunto de distribuciones que se asignan los números de los contenedores, la satisfacción de la restricción, que cada par de números pueden compartir el mismo bin sólo una vez.

Una distribución muy bien puede ser representada por una matriz NxN, en la que cada fila representa un bin. Entonces, el problema es encontrar un conjunto de permutaciones de elementos de la matriz', en el que cada par de números comparte la misma fila sólo una vez. Es irrelevante qué fila es, sólo que los dos números fueron asignados tanto a la misma.

Ejemplo conjunto de 3 permutaciones satisfacer 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 le pertenece en el conjunto anterior:

 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 a múltiples colisiones con la segunda permutación, ya que, por ejemplo, los dos están emparejamiento de 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 manera de producir un conjunto que consta de más sin embargo. Parece ser un problema muy complejo, o un simple problema con una solución no evidente. De cualquier manera Estaría agradecido si alguien tenía alguna idea de cómo resolverlo en un plazo razonable para la N = 8 caso, o se identifique el nombre propio, académica del problema, por lo que podría google para ello.

En el caso de que se preguntan ¿qué es útil para, Busco un algoritmo de planificación para un conmutador de barras cruzadas con 8 memorias intermedias, que sirve a 64 destinos del tráfico. Esta parte del algoritmo de planificación es el tráfico de entrada agnóstico, y conmuta cíclicamente entre un número de asignaciones de búfer de destino cableadas. El objetivo es que cada par de direcciones de destino compiten por el mismo tampón sólo una vez en el período de ciclismo, y para maximizar la duración de ese período. En otras palabras, de modo que cada par de direcciones competía por el mismo tampón que raramente como sea posible.

---

EDIT:

Aquí hay un código que tengo. CÓDIGO

Es codicioso, por lo general termina después de encontrar la tercera permutación. Sin embargo, debe existir un conjunto de al menos N permutaciones que satisfacen el problema.

La alternativa requeriría que la elección de permutación que participa en busca de permutaciones (I + 1..N), para comprobar si la permutación I es parte de la solución que consiste en el máximo número de permutaciones. Eso sería requieren la enumeración de todas las permutaciones de comprobar en cada paso, que es prohibitivamente caro.

Answer 1

Lo que queremos es un combinatoria diseño de bloques. Utilizando la nomenclatura de la página enlazada, desea diseños de tamaño (n ^ 2, n, 1) para una máxima k. Esto le dará n (n + 1) permutaciones, la utilización de su nomenclatura. Este es el máximo teóricamente posible por un argumento de recuento (ver la explicación en el artículo para la derivación de b de v, k, y lambda). existen Tales diseños para n = p ^ k para algunos primo p y número entero k, usando un plano afín. Se conjetura que los únicos aviones afines que existen son de este tamaño. Por lo tanto, si se puede seleccionar n, tal vez esta respuesta será suficiente.

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

Answer 2

Hacer una matriz de 64 x 64 x 8: bool prohibido [i] [j] [k] que indica si el par (i, j) ha aparecido en la fila k. Cada vez que se utiliza el par (i, j) en la fila k, se fijará el valor asociado en esta matriz a uno. Tenga en cuenta que sólo se utilizará el medio de esta matriz para la que i

Para construir una nueva permutación, empezar por tratar el miembro 0, y verificar que al menos siete de prohibido [0] [j] [0] que están sin definir. Si no hay siete izquierda, incremento y vuelve a intentarlo. Repita el procedimiento para llenar el resto de la fila. Repita este proceso para llenar toda la permutación NxN.

Probablemente hay optimizaciones que debería ser capaz de llegar a al implementar esto, pero esto se debe hacer bastante bien.

Answer 3

Posiblemente se podría reformular su problema en la teoría de grafos. Por ejemplo, se empieza con la gráfica completa con N × N vértices. En cada paso, se particiona el gráfico en N, N-camarillas, y a continuación, quitar todos los bordes utilizan.

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

Answer 4

Derecho, el estilo codiciosos no funciona porque se le acaba de números.

Es fácil ver que no puede haber más de 63 permutaciones antes de usted viola la restricción. En la 64, que tendrá que emparejar al menos uno de los números con su ya otra sido emparejados con. El principio del palomar.

De hecho, si se utiliza la tabla de pares prohibidas he sugerido anteriormente, se encuentra que hay un máximo de sólo 1 = 9 permutaciones N + posibles antes de que acabe. La tabla tiene N ^ 2 x (n ^ 2-1) / 2 = 2016 restricciones no redundantes, y cada nuevo permutación creará N x (N elegir 2) = 28 nuevos emparejamientos. Así que todos los emparejamientos serán utilizados después de 2016/28 = 9 permutaciones. Parece que darse cuenta de que hay tan pocos permutaciones es la clave para resolver el problema.

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 permutación de orden n son las diagonales de la permutación n-1 Tes. EDIT: Vaya ... esto sólo 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