Trovare un insieme di permutazioni, con un vincolo

Question

Ho un set di numeri N^2 e N bin. Si suppone che ogni bin abbia numeri N dal set assegnato ad esso. Il problema che sto affrontando è trovare una serie di distribuzioni che mappano i numeri ai bin, soddisfacendo il vincolo, che ogni coppia di numeri può condividere lo stesso bin solo una volta.

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

Esempio impostato su 3 permutazioni soddisfano 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 al set 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 

Poiché di collisioni multiple con la seconda permutazione, poiché, ad esempio, stanno entrambi abbinando 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 da più però. Sembra sia un problema molto complesso, sia un semplice problema con una soluzione non ovvia. In entrambi i casi sarei grato se qualcuno avesse qualche idea su come risolverlo in tempi ragionevoli per il caso N = 8, o identificato il nome accademico corretto del problema, così potrei cercarlo su google.

Nel caso in cui ti stavi chiedendo per cosa è utile, sto cercando un algoritmo di scheduling per uno switch crossbar con 8 buffer, che serve il traffico verso 64 destinazioni. Questa parte dell'algoritmo di schedulazione è indipendente dal traffico di input e passa ciclicamente da un numero di mappature del buffer di destinazione cablate. L'obiettivo è di fare in modo che ogni coppia di indirizzi di destinazione competa per lo stesso buffer una sola volta nel periodo di ciclo e per massimizzare la durata di quel periodo. In altre parole, in modo che ogni coppia di indirizzi competesse per lo stesso buffer il più raramente possibile.

---

EDIT:

Ecco un po 'di codice che ho. CODE

È avido, di solito termina dopo aver trovato la terza permutazione. Ma dovrebbe esistere un insieme di permutazioni di almeno N che soddisfano il problema.

L'alternativa richiederebbe la scelta della permutazione I implicata nella ricerca di permutazioni (I + 1..N), per verificare se la permutazione I è parte della soluzione costituita dal numero massimo di permutazioni. Ciò richiederebbe l'enumerazione di tutte le permutazioni da controllare ad ogni passaggio, il che è proibitivo.

Answer 1

Cosa vuoi è un combinatorial block design. Usando la nomenclatura sulla pagina collegata, vuoi disegni di dimensioni (n^2, n, 1) per massimo k. Questo ti darà permute n (n + 1), usando la tua nomenclatura. Questo è il massimo teoricamente possibile da un argomento di conteggio (vedere la spiegazione nell'articolo per la derivazione di b da v, k e lambda). Tali disegni esistono per n = p^k per alcuni primo p e intero k, usando un piano affine. Si congettura che gli unici piani affini esistenti siano di queste dimensioni. Pertanto, se è possibile selezionare n, forse questa risposta sarà sufficiente.

Tuttavia, se al posto del massimo numero teoricamente possibile di permutazioni, si vuole solo trovare un numero grande (il massimo possibile per un dato n^2), non sono sicuro di quale sia lo studio di questi oggetti .

Answer 2

Creare un array 64 x 64 x 8: bool proibito [i] [j] [k] che indica se la coppia (i, j) è apparsa nella riga k. Ogni volta che usi la coppia (i, j) nella riga k, imposterai il valore associato in questo array a uno. Si noti che si utilizzerà solo la metà di questo array per cui i < j.

Per costruire una nuova permutazione, iniziare provando il membro 0 e verificare che almeno sette di vietato [0] [j] [0] non siano impostati. Se non ne sono rimasti sette, incrementare e riprovare. Ripeti per compilare il resto della riga. Ripeti l'intero processo per riempire l'intera permutazione NxN.

Ci sono probabilmente le ottimizzazioni si dovrebbe essere in grado di elaborare, come si implementa questa, 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 con vertici N × N. Ad ogni passo, dividi il grafico in N-clique e poi rimuovi 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 può non essere impossibile :-)

Answer 4

destro, 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. Al 64 °, dovrai accoppiare almeno uno dei numeri con un altro già abbinato. Il principio del pigeonhole.

Infatti, se si utilizza la tabella delle coppie proibite che ho suggerito in precedenza, si scopre che ci sono un massimo di N + 1 = 9 permutazioni possibili prima che si esaurisca. La tabella ha N^2 x (N^2-1)/2 = 2016 vincoli non ridondanti, e ogni nuova permutazione creerà N x (N scegli 2) = 28 nuovi abbinamenti. Quindi tutti gli abbinamenti verranno utilizzati dopo il 2016/28 = 9 permutazioni. Sembra rendersi conto che ci sono così poche 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 prima riga dell'ennesima permutazione sono le diagonali della permutazione n-1. EDIT: Oops ... questo sembra funzionare solo quando N è primo.

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

A_ij = j * N + i