J'ai un ensemble de nombres n ^ 2 et n bacs. Chaque poubelle est censée avoir n chiffres de l'ensemble assigné. Le problème que je suis confronté est de trouver un ensemble de distributions qui mappent les chiffres aux bacs, satisfaisant la contrainte, que chaque paire de chiffres ne peut partager la même boisson qu'une seule fois.
Une distribution peut être bien représentée par une matrice NXN, dans lequel chaque rangée représente une corbeille. Ensuite, le problème consiste à trouver un ensemble de permutations des éléments de matrice, dans lesquels chaque paire de chiffres partage la même ligne qu'une seule fois. Il n'est pas pertinent que la rangée est, seulement que deux chiffres ont été attribués à la même personne. P>
Exemple d'exemple de 3 permutations satisfaisant la contrainte pour N = 8: P>
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
4 Réponses :
Fabriquez un tableau 64 x 64 x 8: BOOL interdit [i] [j] [k] [k] qui indique si la paire (i, j) est apparue dans la rangée K. Chaque fois que vous utilisez la paire (I, J) de la ligne K, vous définirez la valeur associée dans ce tableau à un. Notez que vous n'utiliserez que la moitié de ce tableau pour lequel je Construire une nouvelle permutation, commencez par essayer le membre 0 et vérifiez qu'au moins sept des [0] [0] [J] [0] non définies. S'il n'y a pas sept parties gauche, incrémentez et essayez à nouveau. Répétez pour remplir le reste de la ligne. Répétez tout ce processus pour remplir l'intégralité de la permutation NXN.
Il y a probablement des optimisations que vous devriez pouvoir trouver au fur et à mesure de votre implémenter cela, mais cela devrait assez bien faire.
+1, mais je pense que la contrainte est plus forte: une fois qu'une paire est apparue dans la même rangée, elles ne peuvent pas apparaître ensemble dans aucune ligne dans une autre permutation. Donc, peut-être que le tableau "interdit" devrait être 64x64, sans la dimension finale?
Une approche gourmande comme celle-ci ne donne qu'un petit nombre de permutations avant de se terminer. C'était la première chose que j'ai essayée.
Peut-être que vous pourriez reformuler votre problème dans la théorie des graphes. Par exemple, vous commencez avec le graphique complet avec n × n sommets. À chaque étape, vous partitionnez le graphique en n n-cliques, puis retirez tous les bords utilisés.
Pour ce cas n = 8, K64 a 64 × 63/2 = 2016 Bords et soixante-quatre lots de K8 ont 1792 bords, donc votre problème peut pas être impossible: -) < / p>
Cela semble correct! Et perspicace - parce que le problème de recherche de clique est connu pour être complet de NP en général. Ce que je soupçonne, c'est que les premières itérations (alors que le graphique NXN est toujours relativement dense) sont probablement faciles à trouver par force brutale, mais comme les bords sont supprimés, les cliques prennent plus de temps et plus à trouver.
Bien, trouver maximal cliques est NP-complet. Je ne suis pas sûr de ce problème. Je pense que les cliques seraient faciles à trouver s'ils existent, car chaque sommet doit être membre d'un, et vous ne souhaitez que la taille N. Le problème est qu'un algorithme gourmand choisira probablement les mauvaises cliques et être incapable Pour trouver tous les N, en supposant que N existent (eh bien, c'est mon intestin sentiment de toute façon).
Oui, essentiellement ce que j'ai mis en œuvre consiste à trouver tous les 8 cliques. Ceci est rapide à avoir 2 permutations de départ (40320 8-cliques trouvées) et faisable à 1 permutation de départ (16 millions de 8-cliques trouvés). Le problème: 1. Enumérant toutes les permutations légales, c'est-à-dire des ensembles de 8 8-cliques, est une affaire de 40320 ^ 8 ou (16 millions) ^ 8. 2. Le nombre de 8-cliques et des permutations possibles dans la prochaine étape dépend du choix de la permutation dans cette étape, gourmand ne fonctionne pas. Une recherche complète aurait besoin de, tout en recherchant la permutation I, évaluez toutes les permutations ultérieures (i + 1..n): /
Ce que vous voulez est un Conception de bloc Combinatorial . Utilisation de la nomenclature sur la page liée, vous souhaitez des conceptions de taille (n ^ 2, n, 1) pour un maximum de k. Cela vous donnera N (N + 1) Permutations, en utilisant votre nomenclature. C'est le maximum théoriquement possible par un argument de comptage (voir l'explication de l'article pour la dérivation de B de V, K et Lambda). De telles conceptions existent pour n = p ^ k pour certains P et ineger K, en utilisant un plan affiné. Il est conjecturé que les seuls avions affins existants sont de cette taille. Par conséquent, si vous pouvez sélectionner n, cette réponse suffira peut-être.
Toutefois, si au lieu du nombre maximal théoriquement possible de permutations, vous voulez simplement trouver un grand nombre (le plus possible pour un n ^ 2 donné), je ne suis pas sûr de l'appel à l'étude de ces objets.
Merci beaucoup! Sur la page Wikipedia pour les conceptions de blocs, j'ai trouvé un lien vers une base de données contenant la solution (64, 8, 1) qui m'intéressait.
Droite, le style gourmand ne fonctionne pas car vous manquez de chiffres.
Il est facile de voir qu'il ne peut y avoir plus de 63 permutations avant de violer la contrainte. Le 64ème, vous devrez associer au moins un des chiffres avec un autre, c'est déjà été jumelé. Le principe du pigeonhole. P>
En fait, si vous utilisez la table des paires interdites, j'ai suggéré plus tôt, vous constatez qu'il y a un maximum de N + 1 N + 1 = 9 permutations possibles avant de s'épuiser. La table a N ^ 2 x (n ^ 2-1) / 2 = 2016 Des contraintes non redondantes et chaque nouvelle permutation créera n x (N choisissez 2) = 28 nouveaux accompagnés. Tous les paires seront donc utilisés après 2016/28 = 9 permutations. Il semble que cela semble se rendre compte qu'il y a si peu de permutations est la clé de résoudre le problème. P>
Vous pouvez générer une liste de n permutations numérotées n = 0 ... N-1 comme p>
A_ij = j * N + i
Vous obtenez également la limite supérieure n + 1 en examinant les voisins N-1 d'une valeur donnée, par exemple. 1. Chacun des chiffres restants n ^ 2-1 ne peut apparaître qu'une seule fois dans une rangée avec 1, ce qui signifie qu'il y en a au plus (n ^ 2-1) / (n-1) = N + 1 rangées uniques, d'où les matrices, contenant 1.
Toute la question est un peu verbal. On ne sait pas ce que vous entendez par paire. Qu'entendez-vous par «la contrainte, que chaque paire de chiffres ne peut partager que le même bac une seule fois.»?
J'ai du mal à comprendre votre contrainte "Chaque paire de chiffres peut partager la même boisson qu'une seule fois". N'est-ce pas trivialement vrai d'un arrangement de N ^ 2 nombres uniques? Pouvez-vous montrer un arrangement qui échoue à la contrainte?
La contrainte doit être satisfaite pour l'ensemble des permutations. De sorte que si une permutation met les chiffres 1 et 2 de la même rangée, aucune autre permutation dans l'ensemble n'est autorisée à mettre 1 et 2 sur la même rangée.
Formellement, laissez P (a, b, i) être le prédicat «A et B apparaissent dans la même ligne de permutation I» et supposons qu'il n'y ait aucune permutations. Ensuite, la contrainte est "Il n'existe pas A, B <= N ^ 2 et I, J <= N telle que p (A, B, I) && P (A, B, J)".
P (a, b, i) peut lui-même être exprimé comme "R (A, I) == R (B, I)", où R est la fonction de mappage de la paire (A, I) au nombre de la ligne dans Quel élément A apparaît dans la permutation i.
Si vous aimez toujours votre code le matin :-), postez-le comme une réponse afin que nous puissions vous uplifier d'autres! C'était un problème vraiment intéressant!