Trovare una serie di permutazioni, con un vincolo

Question

Ho un insieme di N ^ 2 numeri e N bidoni. Ogni scomparto si suppone di avere N numeri dal set ad esso assegnato. Il problema che sto affrontando è trovare una serie di distribuzioni che mappano i numeri per i bidoni, soddisfacendo il vincolo, che ogni coppia di numeri possono condividere lo stesso bin solo una volta.

Una distribuzione può ben essere rappresentata da una matrice NxN, in cui ciascuna riga rappresenta un bidone. Quindi il problema è trovare un insieme di permutazioni di elementi della matrice', in cui ogni coppia di numeri condivide la stessa riga sola volta. È irrilevante quale riga è, solo che due numeri sono stati entrambi assegnati alla stessa.

Esempio set di 3 permutazioni soddisfare il vincolo per 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 permutazione che non appartiene nel set di cui sopra:

 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

A causa delle collisioni multiple con la seconda permutazione, poiché, ad esempio sono entrambi accoppiando i numeri 0 e 32 in una riga.

---

enumerazione tre è facile, è composto da 1 permutazione arbitraria, la trasposizione e una matrice in cui le righe sono fatti di matrice precedente' diagonali.

Non riesco a trovare un modo per produrre un set composto di più però. Sembra essere un problema molto complesso, o un semplice problema con una soluzione non ovvio. In entrambi i casi sarei grato se qualcuno avesse qualche idea come risolverlo in tempo ragionevole per il N = 8 caso, o identificato il corretto, il nome accademico del problema, così ho potuto google per esso.

Nel caso in cui vi sono state chiedendo che cosa è utile per, sto cercando un algoritmo di pianificazione per un crossbar switch con 8 buffer, che serve il traffico verso 64 destinazioni. Questa parte dell'algoritmo di schedulazione è il traffico in ingresso agnostico, e commuta ciclicamente tra un numero di destinazione mappature-tampone cablati. L'obiettivo è di avere ogni coppia di indirizzi di destinazione competere per lo stesso tampone sola volta nel periodo ciclismo, e per massimizzare la lunghezza di tale periodo. In altre parole, in modo che ciascuna coppia di indirizzi è in competizione per lo stesso tampone più raramente possibile.

---

EDIT:

Ecco un po 'di codice che ho. CODICE

E 'avido, di solito termina dopo aver trovato la terza permutazione. Ma ci dovrebbe essere un insieme di almeno N permutazioni che soddisfano il problema.

L'alternativa richiederebbe che la scelta di permutazione ho coinvolto in cerca di permutazioni (I + 1..N), per verificare se permutazione I è parte della soluzione costituita dal numero massimo di permutazioni. Sarebbe richiedono l'enumerazione di tutte le permutazioni di verificare ad ogni passo, che è proibitivo.

Answer 1

Quello che vogliamo è un combinatoria blocco disegno . Secondo la nomenclatura sulla pagina collegata, si vuole disegni di dimensione (n ^ 2, n, 1) per la massima k. Questo vi darà n (n + 1) permutazioni, utilizzando la nomenclatura. Questo è il massimo teoricamente possibile da un argomento conteggio (vedere la spiegazione nell'articolo per la derivazione di b da v, k, e lambda). esistono tali disegni per n = p ^ k per qualche primo p ed un intero k, utilizzando un piano affine. Si congettura che gli unici aerei affine che esistono sono di queste dimensioni. Pertanto, se è possibile selezionare n, forse questa risposta sarà sufficiente.

Tuttavia, se al posto del massimo teoricamente possibile numero di permutazioni, si vuole solo trovare un gran numero (il più possibile per un dato n ^ 2), io non sono sicuro di quello che lo studio di questi oggetti viene chiamato.

Answer 2

Realizzare una matrice 64 x 64 x 8: Bool proibito [i] [j] [k] che indica se la coppia (i, j) è apparso in fila k. Ogni volta che si utilizza la coppia (i, j) nella riga k, si imposterà il valore associato a questa matrice per uno. Si noti che si utilizzerà solo la metà di questo array per il quale i

Per costruire un nuovo permutazione, iniziare cercando l'elemento 0, e verificare che almeno sette proibito [0] [j] [0] che sono disinserito. Se non ci sono sette di sinistra, di incremento e riprovare. Ripetere l'operazione per compilare il resto della riga. Ripetere l'intero processo per riempire l'intero permutazione NxN.

Ci sono probabilmente le ottimizzazioni si dovrebbe essere in grado di elaborare, come si sceglie di implementare questo, ma questo dovrebbe fare abbastanza bene.

Answer 3

Forse si potrebbe riformulare il problema in teoria dei grafi. Ad esempio, si inizia con il grafico completo di N × N vertici. Ad ogni passo, partizionare il grafico in N N-cricche, e quindi rimuovere tutti i bordi usati.

Per questo N = 8 caso, K64 dispone di 64 × 63/2 = 2016 spigoli e sessantaquattro un sacco di K8 hanno 1792 bordi, in modo che il problema possono non è impossibile: -)

Answer 4

A destra, lo stile avido non funziona perché a corto di numeri.

E 'facile vedere che non ci possono essere più di 63 combinazioni prima di violare il vincolo. Sul 64 °, si dovrà associare almeno uno dei numeri con un altro suo già stato associato. Il principio dei cassetti.

In realtà, se si utilizza la tabella di coppie proibiti che ho suggerito in precedenza, si scopre che ci sono un massimo di soli N + 1 = 9 permutazioni possibili prima che si esaurisca. La tabella include N ^ 2 x ^ (N) 2-1 / 2 = 2016 vincoli non ridondanti, e ogni nuovo permutazione creerà N x (N scegliere 2) = 28 nuovi abbinamenti. Così tutti gli abbinamenti saranno utilizzati dopo 2016/28 = 9 permutazioni. Sembra che rendersi conto che ci sono così pochi permutazioni è la chiave per risolvere il problema.

È possibile generare un elenco di permutazioni N numerati n = 0 ... N-1 come

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

che genera una nuova permutazione spostando le colonne in ciascuna permutazione. La riga superiore della permutazione all'ennesimo sono le diagonali della permutazione n-1 °. EDIT: Oops ... questo sembra solo a lavorare quando N è primo.

Questo manca un ultimo permutazione, che si può ottenere trasponendo la matrice:

A_ij = j * N + i