Trouver un ensemble de permutations, avec une contrainte

Question

J'ai un ensemble de N^2 chiffres et N bacs.Chaque bac est censé avoir de N nombres à partir de l'ensemble lui est assigné.Le problème, je suis confronté est de trouver un ensemble de distributions de la carte les numéros pour les bacs, en satisfaisant la contrainte, que chaque paire de nombres peuvent partager la même cellule qu'une seule fois.

Une distribution peut bien être représenté par une matrice NxN, dans lequel chaque ligne représente une poubelle.Ensuite, le problème est de trouver un ensemble de permutations de la matrice d'éléments, dans lequel chaque paire de nombres d'actions de la même ligne qu'une seule fois.Il est sans importance que les lignes qui il est, mais seulement que deux numéros ont été assignée à la fois pour le même.

Exemple ensemble de 3 permutations satisfaisant la contrainte pour 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

Une permutation qui n'appartient pas à l'ensemble ci-dessus:

 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

En raison de collisions multiples avec la deuxième permutation, puisque, par exemple, ils sont à la fois l'appariement des nombres de 0 et 32 dans une rangée.

---

L'énumération des trois est facile, il se compose de 1 arbitraire, de permutation, de sa transposition et une matrice dont les lignes sont faites de la précédente matrice " diagonales.

Je ne peux pas trouver un moyen de produire un ensemble consistant de plus de bien que.Il semble être un problème très complexe, ou un problème simple avec une solution non évidente.De toute façon, je serais reconnaissant si quelqu'un avait des idées comment le résoudre dans un délai raisonnable pour les N=8 cas, ou identifié la bonne, nom académique du problème, afin que je puisse google pour elle.

Dans le cas où vous vous demandez ce qui est utile, je suis à la recherche d'un algorithme d'ordonnancement pour un crossbar switch avec 8 tampons, qui sert à la circulation de 64 destinations.Cette partie de l'algorithme d'ordonnancement est l'entrée de la circulation agnostique, et les commutateurs de manière cyclique entre un certain nombre de filaires destination-tampon mappages.L'objectif est que chaque paire d'adresses de destination en concurrence pour le même tampon qu'une seule fois dans le cycle de la période, et de maximiser la période de la longueur.En d'autres termes, de sorte que chaque paire d'adresses a été en compétition pour le même tampon que rarement que possible.

---

EDIT:

Voici un code que j'ai.CODE

Il est gourmand, il se termine généralement après la recherche de la troisième permutation.Mais il doit exister un ensemble d'au moins N permutations satisfaisant le problème.

L'alternative serait d'exiger que le choix de permutation j'ai participé à la recherche pour les permutations (I+1..N), pour vérifier si la permutation de I est une partie de la solution comprenant au maximum le nombre de permutations.Que j'avais besoin d'énumérer tous les permutations de vérifier à chaque étape, ce qui est prohibitif.

Answer 1

Ce que vous voulez, c'est un combinatoire conception de bloc.À l'aide de la nomenclature sur la page liée, vous voulez des dessins de taille (n^2, n, 1) pour un maximum de k.Cela vous donnera n(n+1) permutations, à l'aide de votre nomenclature.Ce qui est le maximum possible, en théorie, par un argument de comptage (voir l'explication dans l'article pour le calcul de la b de v, k, et lambda).De tels modèles existent pour n = p^k pour certains, le premier p et k entier, à l'aide d'un plan affine.Il est conjecturé que la seule affine plans qui existent sont de cette taille.Par conséquent, si vous pouvez sélectionner n, peut-être que cette réponse suffit.

Toutefois, si, au lieu de le maximum possible, en théorie, le nombre de permutations, vous voulez juste trouver un grand nombre (la plupart que vous pouvez pour un n^2), je ne suis pas sûr de ce que l'étude de ces objets est appelé.

Answer 2

Faire un 64 x 64 x 8 tableau:bool interdit[i][j][k] qui indique si la paire (i,j) est apparu dans la ligne k.Chaque fois que vous utilisez la paire (i, j) dans la ligne k, vous allez définir la valeur associée dans ce tableau à une.Notez que vous devrez utiliser uniquement la moitié de ce tableau pour lequel je < j.

Pour construire une nouvelle permutation, commencez par essayer les états 0 et vérifiez qu'au moins sept des interdits[0][j][0] qui ne sont pas définis.Si il n'y a pas sept à gauche, l'accroissement et essayez à nouveau.Répétez pour remplir le reste de la ligne.Répétez ce processus pour remplir la totalité de NxN permutation.

Il y a probablement des optimisations, vous devriez être capable de trouver avec vous le mettre en œuvre, mais cela devrait le faire assez bien.

Answer 3

Peut-être que tu pourrais reformuler votre problème dans la théorie des graphes.Par exemple, vous commencez par le graphe complet à N×N sommets.À chaque étape, vous partition du graphe en N N-cliques, puis retirez toutes les arêtes sont utilisés.

Pour cette N=8 cas, K64 a 64×63/2 = 2016 bords, et soixante-quatre lots de K8 ont 1792 bords, de sorte que votre problème peut pas impossible :-)

Answer 4

À droite, le gourmand de style ne fonctionne pas parce que vous manquez de nombres.

Il est facile de voir qu'il ne peut pas être plus de 63 permutations avant de violation de la contrainte.Sur la 64e, vous devrez paire au moins un des numéros avec un autre de ses déjà été jumelé avec.Le casier principe.

En fait, si vous utilisez le tableau de interdit paires je l'ai suggéré précédemment, vous trouvez qu'il y a un maximum de N+1 = 9 permutations possibles avant de vous lancer.La table a N^2 x (N^2-1)/2 = 2016 non-contraintes redondantes, et chaque nouvelle permutation créera N x (N choisissez 2) = 28 nouvelles alliances.Donc, tous les appariements seront utilisés après 2016/28 = 9 permutations.Il semble que de réaliser qu'il y a si peu de permutations est la clé pour résoudre le problème.

Vous pouvez générer une liste de N permutations numéroté n = 0 ...N-1 comme

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

ce qui génère une nouvelle permutation en déplaçant les colonnes dans chaque permutation.La ligne du haut de la nième permutation sont les diagonales de la n-1ème permutation.EDIT:Oups...cela ne semble fonctionner lorsque N est premier.

Ce manque une dernière permutation, que vous pouvez obtenir par la transposition de la matrice:

A_ij = j * N + i