Finden einer Reihe von Permutationen, mit einer Nebenbedingung

Question

Ich habe eine Reihe von N^2 Nummern und N Bins. Jeder Behälter soll N Nummern von dem ihm zugewiesenen Satz haben. Das Problem, dem ich gegenüberstehe, besteht darin, eine Reihe von Verteilungen zu finden, die die Zahlen den Bins zuordnen und die Bedingung erfüllen, dass jedes Zahlenpaar dieselbe Zelle nur einmal gemeinsam nutzen kann.

Eine Verteilung kann schön durch eine NxN-Matrix dargestellt werden, in der jede Zeile eine Bin darstellt. Dann besteht das Problem darin, eine Menge von Permutationen der Matrixelemente zu finden, in denen jedes Zahlenpaar die gleiche Zeile nur einmal teilt. Es ist irrelevant, welche Zeile es ist, nur dass zwei Nummern demselben zugeordnet wurden.

Beispielsatz von 3 Permutationen Erfüllen der Randbedingung für 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 

Eine Permutation, die in dem obigen Satz gehört nicht:

 
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 

Weil von mehreren Kollisionen mit der zweiten Permutation, da sie zum Beispiel beide die Zahlen 0 und 32 in einer Reihe paaren.

---

Aufzählen von drei ist einfach, es von 1 beliebiger Permutation besteht, deren Umsetzung und eine Matrix, wo die Zeilen der vorhergehenden Matrix‘Diagonalen vorgenommen werden.

Ich kann keinen Weg finden, um ein Set bestehend aus mehr zu erzeugen. Es scheint entweder ein sehr komplexes Problem oder ein einfaches Problem mit einer nicht naheliegenden Lösung zu sein. Wie auch immer, ich wäre dankbar, wenn jemand Ideen hätte, wie ich es in angemessener Zeit für den N = 8 Fall lösen könnte, oder ich identifizierte den richtigen akademischen Namen des Problems, also könnte ich danach googlen.

Falls Sie sich fragen, wofür es nützlich ist, suche ich nach einem Zeitplanungsalgorithmus für einen Crossbar-Switch mit 8 Puffern, der Verkehr zu 64 Zielen bedient. Dieser Teil des Scheduling-Algorithmus ist verkehrsunabhängig eingegeben und schaltet zyklisch zwischen einer Anzahl festverdrahteter Zielpufferzuordnungen um. Das Ziel besteht darin, jedes Paar Zieladressen nur einmal in der Zyklusperiode um denselben Puffer konkurrieren zu lassen und die Länge dieses Zeitraums zu maximieren. Mit anderen Worten, so dass jedes Adressenpaar so selten wie möglich um denselben Puffer konkurrierte.

---

EDIT:

Hier einige Code, den ich habe. CODE

Es ist gierig, es endet normalerweise nach dem Finden der dritten Permutation. Aber es sollte eine Menge von mindestens N Permutationen geben, die das Problem erfüllen.

Die Alternative würde erfordern, dass die Wahl der Permutation Ich Suche nach Permutationen (I + 1..N), um zu prüfen, ob Permutation I Teil der Lösung, bestehend aus der maximalen Anzahl von Permutationen. Das würde erfordern, alle Permutationen aufzulisten, um bei jedem Schritt zu überprüfen, was unerschwinglich teuer ist.

Answer 1

Was Sie wollen, ist ein combinatorial block design. Mithilfe der Nomenklatur auf der verknüpften Seite möchten Sie Designs der Größe (n^2, n, 1) für maximale k. Dies wird Ihnen n (n + 1) Permutationen geben, unter Verwendung Ihrer Nomenklatur. Dies ist das theoretisch mögliche Maximum eines Zählarguments (siehe die Erläuterung im Artikel zur Ableitung von b aus v, k und lambda). Solche Designs existieren für n = p^k für einige Primzahlen p und ganze k unter Verwendung einer affinen Ebene. Es wird vermutet, dass die einzigen affinen Ebenen, die existieren, diese Größe haben. Wenn Sie also n auswählen können, ist diese Antwort möglicherweise ausreichend.

Wenn Sie jedoch statt der theoretisch maximal möglichen Anzahl von Permutationen nur eine große Zahl finden möchten (die meisten können Sie für ein gegebenes n^2), bin ich nicht sicher, was das Studium dieser Objekte heißen soll .

Answer 2

Bilden Sie ein 64 x 64 x 8 Array: bool verboten [i] [j] [k] was anzeigt, ob das Paar (i, j) in Zeile k erschienen ist. Jedes Mal, wenn Sie das Paar (i, j) in der Zeile k verwenden, setzen Sie den zugehörigen Wert in diesem Array auf Eins. Beachten Sie, dass Sie nur die Hälfte dieses Arrays für die i < j verwenden.

Um eine neue Permutation zu erstellen, versuchen Sie zunächst das Element 0 und überprüfen Sie, ob mindestens sieben Verbotene [0] [j] [0] nicht gesetzt sind. Wenn nicht noch sieben übrig sind, erhöhen Sie den Wert und versuchen Sie es erneut. Wiederholen Sie den Vorgang, um den Rest der Zeile auszufüllen. Wiederholen Sie diesen ganzen Prozess, um die gesamte NxN-Permutation zu füllen.

Es gibt wahrscheinlich Optimierungen, die Sie in der Lage sein sollten, wenn Sie dies implementieren, aber das sollte ziemlich gut tun.

Answer 3

Möglicherweise könnten Sie Ihr Problem in Graphtheorie umformulieren. Sie beginnen beispielsweise mit dem vollständigen Graphen mit N × N-Eckpunkten. Bei jedem Schritt partitionieren Sie den Graphen in N N-Cliquen und entfernen dann alle verwendeten Kanten.

Für diesen N = 8 Fall hat K64 64 × 63/2 = 2.016 Kanten und vierundsechzig viele K8 haben 1.792 Kanten, so dass Ihr Problem kann nicht unmöglich sein :-)

Answer 4

Richtig, der gierige Stil funktioniert nicht, weil Ihnen die Zahlen ausgehen.

Es ist leicht zu sehen, dass es nicht mehr als 63 Permutationen geben kann, bevor Sie die Einschränkung verletzen. Am 64. musst du mindestens eine der Zahlen mit einer anderen paaren, mit der bereits gepaart wurde. Das Schubladenprinzip.

In der Tat, wenn Sie die Tabelle der verbotenen Paare, die ich zuvor vorgeschlagen, Sie finden, dass es ein Maximum von nur N + 1 = 9 Permutationen möglich, bevor Sie ausgehen. Die Tabelle hat N^2 x (N^2-1)/2 = 2016 nicht-redundante Nebenbedingungen, und jede neue Permutation erzeugt N x (N wähle 2) = 28 neue Paarungen. So werden alle Paarungen nach 2016/28 = 9 Permutationen aufgebraucht. Es scheint, als würde man erkennen, dass es so wenige Permutationen gibt, ist der Schlüssel zur Lösung des Problems.

Sie können eine Liste von N Permutationen numerierten erzeugen n = 0 ... N-1 als

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

die durch Verschieben der Spalten in jeder Permutation eine neue Permutation erzeugt. Die obere Reihe der n-ten Permutation sind die Diagonalen der n-1ten Permutation. EDIT: Hoppla ... das scheint nur zu funktionieren, wenn N prim ist.

Diese vermisst eine letzte Permutation, die man durch die Umsetzung der Matrix erhalten kann:

A_ij = j * N + i