Die Suche nach einer Reihe von Permutationen, mit einer Einschränkung

Question

Ich habe eine Reihe von N ^ 2 Zahlen und N Bins. Jeder Behälter soll N Zahlen aus der Menge ihm zugewiesen haben. Das Problem, das ich mit Blick auf bin, ist eine Reihe von Distributionen zu finden, um die Zahlen zu den Fächern, erfüllt die Bedingung abzuzubilden, dass jedes Paar von Zahlen kann nur einmal das gleiche ist teilen.

Eine Verteilung kann gut durch eine NxN-Matrix dargestellt werden, wobei jede Zeile einen Behälter darstellt. Dann wird das Problem, einen Satz von Permutationen der Elemente ‚Matrix zu finden, in dem jedes Zahlenpaar nur einmal dieselbe Zeile teilt. Es ist unerheblich, welche Zeile es ist, nur dass zwei Zahlen auf den gleichen beide zugewiesen 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

Durch mehrere Kollisionen mit der zweiten Permutation, da beispiels sie Paarung sowohl die Zahlen 0 und 32 in einer Zeile.

---

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

Ich kann nicht einen Weg finden, um einen Satz zu produzieren, obwohl mehr aus. Es scheint, entweder ein sehr komplexes Problem, oder ein einfaches Problem mit einer nicht offensichtlichen Lösung. So oder so würde ich dankbar sein, wenn jemand irgendwelche Ideen hat, wie es in angemessener Zeit für die N = 8 Fall zu lösen, oder die eigentlichen wissenschaftlichen Namen des Problems identifiziert, so konnte ich für Google es.

Falls Sie sich fragen, was es ist geeignet, ich bin auf der Suche nach einem Scheduling-Algorithmus für einen Crossbar-Switch mit 8 Puffer, der Verkehr zu 64 Zielen dient. Dieser Teil des Planungsalgorithmus eingegeben Verkehrsunabhängig und schaltet zyklisch zwischen einer Anzahl von fest verdrahteten destination-Pufferzuordnungen. Das Ziel ist, jedes Paar von Zieladressen für den gleichen Puffer in der Einfahrphase nur einmal im Wettbewerb zu haben, und diese Frist Länge zu maximieren. Mit anderen Worten, so dass jedes Paar von Adressen für den gleichen Puffer so selten wie möglich konkurriert.

---

EDIT:

Hier ist ein Code, den ich habe. CODE

Es ist gierig, es endet in der Regel nach dem dritten Permutation zu finden. Aber es sollte eine Reihe von mindestens N Permutationen existieren erfüllt das Problem.

Die Alternative würde erfordern, dass Permutation Auswahl ich für Permutationen beteiligt suchen (I + 1..N), zu überprüfen, ob Permutation ich Teil der Lösung ist, die aus der maximalen Anzahl von Permutationen. Das würde erfordern, dass alle Permutationen Aufzählen bei jedem Schritt zu überprüfen, die unerschwinglich teuer ist.

Answer 1

Was Sie wollen, ist ein kombinatorischen Block-Design . Unter Verwendung der Nomenklatur auf der verlinkten Seite möchten Sie Entwürfe Größe (n ^ 2, n, 1) für maximal k. Dies gibt Ihnen n (n + 1) Permutationen, mit Ihrer Nomenklatur. Dies ist die maximale theoretisch möglich, durch eine Zählargument (siehe die Erläuterung in dem Artikel für die Ableitung von b v, k, und lambda). Solche Konstruktionen existieren für n = p ^ k für einige Primzahl p und k ganze Zahl ist, eine affine Ebene verwendet. Es wird vermutet, dass die einzigen affinen Ebene, die diese Größe vorhanden ist. Deshalb, wenn Sie n wählen können, vielleicht wird diese Antwort genügen.

Wenn jedoch statt der theoretisch maximal möglichen Anzahl von Permutationen, Sie wollen einfach nur eine große Anzahl finden (die man für eine gegebene n ^ 2), ich bin nicht sicher, was die Untersuchung dieser Objekte genannt wird.

Answer 2

Sie eine 64 x 64 x 8-Anordnung: Verboten bool [i] [j] [k] das anzeigt, ob das Paar (i, j) in Reihe k erschienen ist. Jedes Mal, wenn das Paar verwenden (i, j) in der Zeile k, werden Sie den zugehörigen Wert in diesem Array auf eines gesetzt. Beachten Sie, dass Sie nur die Hälfte dieses Array verwenden, für die i

eine neue Permutation zu konstruieren, beginnen, indem das Element versuchen 0, und stellen Sie sicher, dass mindestens sieben der verbotenen [0] [j] [0], die nicht gesetzt sind. Wenn es nicht sieben links, erhöhe sind und versuchen Sie es erneut. Wiederholen Sie den Rest der Zeile auszufüllen. Wiederholen Sie diesen gesamten Prozess die gesamte NxN Permutation zu füllen.

Es gibt wahrscheinlich Optimierungen Sie sollen kommen können, wie Sie dies umsetzen, aber das sollte ziemlich gut.

Answer 3

Vielleicht könnten Sie Ihr Problem in der Graphentheorie neu zu formulieren. Zum Beispiel beginnen Sie mit dem vollständigen Graphen mit N × N Ecken. Bei jedem Schritt Sie das Diagramm in N N-Cliquen partitionieren, und entfernen Sie dann alle Kanten verwendet.

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 können nicht unmöglich sein: -)

Answer 4

Richtig, der gierige Stil funktioniert nicht, weil Sie aus Zahlen ausgeführt werden.

Es ist leicht zu sehen, dass es nicht mehr als 63 Permutationen sein kann, bevor Sie die Einschränkung verletzen. Auf dem 64th, werden Sie mindestens eine der Zahlen mit einem anderen seiner bereits gepaart mit paaren haben. Das Schubfachprinzip.

In der Tat, wenn man die Tabelle der verbotenen Paare verwendet ich bereits weiter oben erwähnt, finden Sie, dass es maximal nur N + 1 = 9 Permutationen möglich, bevor Sie ausgehen. Die Tabelle hat N ^ 2 x (N ^ 2-1) / 2 = 2016 nicht redundante Einschränkungen, und jede neue Permutation wird N x (N wählen, 2) = 28 neue Paarungen erstellen. So werden alle Paarungen bis nach 2016/28 = 9 Permutationen verwendet werden. Es scheint so zu realisieren, dass es so wenige Permutationen der Schlüssel zur Lösung des Problems ist.

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

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

, die erzeugt eine neue Permutation durch die Spalten in jeder Permutation zu verschieben. Die obere Reihe der n-ten Permutation sind die Diagonalen der n-1-te Permutation. EDIT: Oops ... scheint dies nur zu funktionieren, wenn N eine Primzahl ist.

Dieses vermisst eine letzte Permutation, die man durch die Umsetzung der Matrix erhalten können:

A_ij = j * N + i