Je savais pas trop quoi mettre comme titre tellement je trouve rien sur internet...
Imaginez un groupe de personnes: N
Je veux répartir toutes ses personnes dans des groupes de k personnes. (naturellement, N doit être divisible entier par k)
jusqu'a là, c'est facile.
Maintenant, je veux refaire une répartition dans des nouveaux groupes de k personnes pour que chacun soit avec des nouvelles personnes.
Et ainsi de suite jusqu'à temps que chaque personne ait pu voir toutes les autres personnes dans un groupe.
On peut dire que c'est un peu comme si on essayais de générer un championnat mais pas 1 contre 1 mais plusieurs personnes dans une rencontre.
Ca ressemble un peu aux combinaisons mais pas tout a fait.
Je veux pas savoir le nombre de combinaison de k personnes parmi N.
J'aimerais savoir le nombre d'itération maximum que l'on peut faire pour N et k donné. Et aussi s'il existait un algorithme permettant de répartir les différentes personnes sans réparations.
Si je prend un exemple facile: 9 personnes dans des groupes de 3: on trouve 4 itérations.
1= (A1, A2, A3), (B1, B2, B3), (C1, C2, C3)
2= (A1, B1, C1), (A2, B2, C2), (A3, B3, C3)
3= (A1, B2, C3), (A2, B3, C1), (A3, B1, C2)
4= (A1, B3, C2), (A2, B1, C3), (A3, B2, C1)
Cela semble plus facile quand le nombre de personnes N = k^2 (puissance)
Aussi, pour une personne donné, on sait déjà qu'il faut (N - 1) / (k - 1) itérations pour qu'elle puisse rencontrer toutes les autres personnes
En écrivant cette dernière phrase, je me rend compte que je viens de répondre partiellement à ma première question.
Si on considère 12 personnes toujours dans des groupes de 3. (12-1)/(3-1) = 5.5 ... donc il peut y avoir 5 itérations sans répétitions.
Ce que j'ai pas est si ce nombre de 5 est possible en considérant la répartition de tout le monde ?
Pour l'algorithme, il est relativement simple quand on a N = K^2 ..
On peut d'ailleurs déjà dire que quand N < k^2 , on ne peut faire qu'une itération de groupe sans répétition.
Mais quand N > k^2, j'Ai du mal a trouver un algorithme correct
Si je pose N=6 et k=3, j'aurai au départ: (A1, A2, A3) (B1, B2, B3) J'ai N (6) < k^2 (3^2=9) Comment je peux répartir en une seule itération? Pour l'algorithme, une première ébauche serait la suivante: Je fais la liste des personnes connues par chaque personne. Je peux supposer au départ que chaque personne n'en connais aucune autre. Je construit des groupes vides et j'essaie de placer les personnes. Dans chaque groupe, la première est facile à placer. Pour les autres, si la personne connait les précédentes, je saute à une autre personne. Sinon, je place la personne dans le groupe. Je ne sais pas, si à partir de ce point, si je ne trouve aucune nouvelle personne, c'est que tout le monde a rencontré tout le monde ... Si k=3, chaque personne en connaitra 2 autres. Ce qui suppose que N-1 est pair. Donc la condition est trop forte. Si au moins une personne est nouvelle, ça pose problème si on ne trouve aucune personne. Qui est en trop? Pas forcément la dernière. On devra trouver un algorithme de traceback dans ce cas. Quand le groupe est rempli, je modifie la liste de chaque personne pour tenir compte des nouvelles connaissances. je passe au groupe suivant. Quand tous les groupes sont remplis, j'affiche la nouvelle répartition. Et je recommence avec de nouveaux groupes vides. Ici, si une personne connait toutes les autres, je suppose qu'elles se connaissent toutes. L'algorithme se termine.
Le Tout est souvent plus grand que la somme de ses parties.
Si je pose N=6 et k=3, j'aurai au départ: (A1, A2, A3) (B1, B2, B3) J'ai N (6) < k^2 (3^2=9) Comment je peux répartir en une seule itération?
A la 2e itération, il y aura forcément des doublons. C'est impossible de répartir avec que des personnes différentes.
J'avais également cela comme algorithme.. mais le traceback est pas si simple...
Mettons 36 personnes dans des groupes de 6: nous obtenons 6 groupes.
Pour une personne donné: (N - 1) / (k - 1) = 35 / 5 = 7. Donc 7 itérations
La répartition de la 1ere répartition est fait aléatoirement ensuite, on peut nommer chaque groupe: A,B,C,D,E,F . 6 personnes dans chaque groupe. on peut nommer les personnes A1, A2 ... F5, F6
A partir de la 2e itération, c'est logique que chaque personne dans un groupe proviendra d'un groupe différent du 1er groupe: donc une personne de A,B,C,D,E et F ensemble.
Pour que chaque A rencontre chaque B, il faut 36 combinaisons... divisé par le nombre de groupes: 6. On retombe sur 6 itérations (+ celle du début = 7)
tJ'ai commencé à écrire un programme en Python devant correspondre à l'algorithme. Je ne prétend pas qu'il fonctionne. Le traceback me semble beaucoup plus compliqué que je pensais. Ensuite, quand je place un nouveau dans un groupe, je me demande plutôt si au moins un des autres ne le connait pas. Je pense que tu exigeais que aucun ne le connaisse, mais mon code ne marche pas avec cette contrainte. Le programme ne semble pas pouvoir trouver de solution si N différent de k² Il ne marche pas pour N=16 et k=4 alors qu'il devrait. Pour les autres carrés, le nombre d'itérations semble correspondre à ta formule: (N-1) / (k-1) Exemples: 2|4:3, 3|9:4, 5|25:6, 6|36:7, 49|7:8 Le nombre de possibilités nous amène au nombre k suivant. J'ai simplement identifié les personnes par un nombre de 0 à N-1. Voici la solution pour N=25 et k=5: [[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]] [[0, 5, 6, 7, 8], [9, 10, 11, 12, 13], [14, 15, 16, 17, 18], [19, 20, 21, 22, 23], [24, 1, 2, 3, 4]] [[0, 9, 10, 11, 12], [13, 15, 16, 17, 18], [19, 24, 1, 2, 3], [4, 5, 6, 7, 8], [14, 20, 21, 22, 23]] [[0, 13, 14, 15, 16], [17, 20, 21, 22, 23], [24, 5, 6, 7, 8], [9, 18, 19, 1, 2], [3, 10, 11, 12, 4]] [[0, 17, 18, 19, 20], [21, 1, 2, 3, 4], [5, 10, 11, 12, 13], [14, 24, 6, 7, 8], [9, 15, 16, 22, 23]] [[0, 21, 22, 23, 24], [1, 5, 6, 7, 8], [9, 14, 17, 19, 20], [2, 10, 11, 12, 13], [15, 3, 4, 16, 18]]
Le Tout est souvent plus grand que la somme de ses parties.
comme ça de but en blanc sans trop y avoir réfléchit, je me dirigerai sans doute vers une solution à base de parcours graphe :
Dans ce graphe non dirigé chaque sommet représentera une personne, deux sommets sont reliés par une arrête uniquement si elles n'ont jamais été dans un même groupe. Donc dans l'exemple le graphe de départ sera K36.
Ensuite l'idée de l'algo est relativement simple :
pour chaque sommet s du graphe G qui n'est pas marqué
créer un groupe avec s et (n-1) de ses voisins
marquer tous les sommets du groupe
effacer les arrêtes reliant deux sommets quelconques du groupe
Il faut évidemment réinitialiser les marques avant chaque application de l'algo, dans lequel G est ledit graphe et n la taille des groupes.
A priori, en raffinant un peu les cas limites, ça devrait même donner des résultats corrects avec des groupes de tailles hétérogènes, ou d'autres contraintes de départ comme tout le monde doit affronter tout le monde sauf les membres de sa famille (ça fait des arrêtes en moins dans le graphe de départ), …
À vue de nez je dirais que les complexités temporelle et spatiale sont en O(|S|²), avec S l'ensemble des sommets.
Edit: en y réfléchissant plus, mon algo n'est pas correct. En effet il faut également que chacun des voisins choisis soit en relation avec les autres … cela correspond à trouver un sous-graphe complet de taille du groupe →problème de la clique de taille fixe qui toujours polynomial en temps mais l'exposant est la taille du groupe …
Si N=k², et k est un nombre premier, il est très facile de mettre en place un tel 'tournoi' avec k+1 étapes.
Et tout le monde aura vu tout le monde , grâce à l'identité remarquable N-1=(k-1)(k+1)
Si N=k² et k un nombre non premier, il y a a priori une solution parfaite, mais la mise en place est plus difficile (et je ne suis pas sûr que ce soit toujours possible)
t@White Crow: Ta méthode semble élégante à première vue mais pas forcément évidente à coder. Enfin, je n'y ai pas réfléchi très longtemps. Je suis en train de repenser une méthode heuristique, bête et méchante, qui utiliserait plus facilement le backtracking que ce que j'ai déjàfait. J'utilise un dictionnaire en Python avec comme valeur un set contenant les personnes connues. Un truc tordu est que si une personne se connait elle-même, c'est qu'elle fait partie d'un autre groupe. Donc, je ne la choisis pas. Quand je fais le backtracking, je dois défaire ces nouvelles connaissances, y compris pour soi-même.
Le Tout est souvent plus grand que la somme de ses parties.
tDe la façon dont je le faisais, c'est normal de trouver des doublons. Je sais que ce n'est pas ce que tu cherches. Je suis en train de modifier mon code. Je vais exiger que chaque personne n'aient jamais rencontré les autres personnes du groupe. Pour le backtracking: Au moment où tu as accepté une personne dans le groupe: + tu as vérifié qu'elles ne se connaissaient pas avant. + tu as ajouté chaque personne dans la liste des connaissances de chacun. a connait maintenant b, et b connait maintenant a Au moment où tu recules: + tu efface de la liste des connaissances ceux du groupe en enlevant chaque élément. + tu dois le faire dans les deux sens: a ne connait plus b, et b ne connait plus a. Qui choisir comme alternative pour une personne? Je vais essayer celles dont le numéro est supérieur au numéro courant en vérifiant qu'elle n'est pas déjà dans un groupe. (j'avais essayé avec des sous-listes cycliques, mais c'est trop compliqué et ça ne marche pas) Si je ne peux pas en trouver, je recule encore. Je ne sais pas si c'est assez clair ... (mes activités et obligations personnelles me ralentissent)
Le Tout est souvent plus grand que la somme de ses parties.
je tente de quoi aussi (je connais pas le python par contre mais en c#)
Mon approche est différente (avec N=k²).
Avec mon N=36 et k=6 (mon vrai probleme est avec N=42 et k=6 mais je suis pas sur que l'algo fonctionne ainsi).
Je sépare dés le début en différent groupe et je garde chaque groupe avec sa liste de personnes
On sait (avec une identité parfait) qu'une personne doit rencontre une autre personne de chaque groupe, donc on limite les choix:
On part du 1er groupe et on prend la 1ere personne disponible.
Ensuite on passe au 2e groupe et on prend la 1ere personne jamais rencontré
Ensuite au 3e groupe, on prend la 1ere personne jamais rencontré par les deux personnes déjà là
etc.
Si on trouve personne disponible dans un des groupes, il faut enlever la dernière personne mise et en trouver une autre de son groupe (et faire le traceback de la sorte)
Si le groupe en formation est impossible à former, il faut modifier quelque chose dans le groupe précédent: idéalement, pour être plus intelligent, il faudrait déterminer le groupe initial dont il était pas possible de prendre une personne.
En résumé:
on forme les groupes initiaux:
gr1: {1,2,3,4,5,6}
gr2: {7,8,9,10,11,12}
gr3: {13,14,15,16,17}
etc.
On compte cela comme la 1ere itération. A noter que si N < k^2 , ce sera la seule itération possible.
Pour les itérations suivantes, on parcours les groupes initial séquentiellement en prenant une personne dans chaque groupe pour former les groupes de la séquence 2.
L'itération ne pose pas de problème si N = k^2 (les 1er de chaque groupe ensemble, ensuite les seconds, etc.)
Je viens de tout lire, ça a l'air drôlement compliqué et je n'ai pas la motivation pour étudier ce casse-tête... Disons que je viens d'essayer avec trois groupes de deux et je ne suis déjà même pas sûr que ce soit possible (*).
Je voulais juste faire une remarque : pour que ça marche, il est nécessaire que le nombre de groupes soit supérieur ou égal au nombre d'équipiers par groupe.
Démonstration : notons Ng le nombre de groupes (N = Ng × k).
− À l'étape 1, j'ai k-1 coéquipiers.
− À l'étape 2, il me faut k-1 nouveaux coéquipiers provenant des Ng-1 autres groupes, et ils doivent tous provenir de groupes différents. Donc Ng-1 ≥ k-1.
− Conclusion : l'étape 2 nécessite que Ng ≥ k.
Ah, je viens de m'apercevoir que c'est équivalent à N < k² que tu as indiqué juste au-dessus (puisque N = Ng × k).
-------
(*) Ah si :
AB-CD-ED
AC-BE-DF
AD-EC-BF
AE-BD-CF
AF-BC-DE
Voilà : si tu organises des compétitions en duo (courses en tandem, double au tennis ou au ping pong, catch à quatre...) ça pourra te servir. (En fait c'est équivalent à trouver les cinq journées d'un championnat à six, chaque couple correspondant aux adversaires. Du coup ce n'est pas difficile, et j'ai fait ça avec un petit graphique.)
Le nombre de groupes est en effet N/k et le nombre de personnes par groupe est k. donc k <= N/k ou N > k² L'exemple que je donnais avec N=6 et k=3 ne marchera pas. Je n'ai pas encore été capable de faire fonctionner mon code. Le backtracking n'est pas évident. Une chance que je le fais en Python. Ce serait affreux en C ...
Le Tout est souvent plus grand que la somme de ses parties.
J'ai toujours pas résolu ce problème... ca me stress lol.
J'ai moi même fait un programme qui a l'Air d'être correct sauf que:
9 personnes dans groupes de 3= 4 itération= OK
16 personnes dans groupes de 4 = 5 itérations = OK
25 personnes dans groupes de 5 = seulement 3 itérations trouvé... cela me semble bizarre
36 personnes dans groupes de 6 = également que 3 itérations trouvé...
Maintenant si je ne respecte pas la régle du N = k au carré:
12 personnes dans 4 groupes de 3 = ca me calcule seulement 3 itérations. J'essaie de contre vérifier à la main mais je me serais attendu à au moins 4 personnelement
15 personnes dans 5 groupes de 3 = 5 itérations
18 personnes dans 5 groupes de 3 = aprés 5 itérations trouvé, dans la 6e, le programme pateauge et se termine pas... comme dans une récursion infinie...
20 personnes dans 5 groupes de 4 = dés la 2e itération, le programme tourne en boucle...
J'ai du mal à détecter le probleme, autant avec 25,5 ou 36,6 ... il ne trouve que 3 résultats ce qui me semble pas crédible... et dans l'essai du 4e résultat, la récursion n'a pas l'air de planter
Alors qu'a côté, avec moins de personnes, ca plante...
Pour chaque personne, je conserve la liste de personnes connues de lui même. Donc a la fin du programme, j'Affiche également la liste de personnes non connues de chacun
Je ne plante pas avec mon code actuel, mais j'ai encore de la difficulté avec le backtracking. Moi aussi, j'obtiens des résultats partiels. Si on se refère à la séquence que je donnais, il y a progression quand k augmente et N = k² C'est comme s'il n'y avait pas de place pour des solutions comme k=6 et N=42 Le quotient donne: (42-1)/(6-1) = 41/5 = 8.2 Le fait que ce ne soit pas un entier veut-il dire que la solution n'est pas possible?
Le Tout est souvent plus grand que la somme de ses parties.
J'ai compris d'ou venait le problème dans le programme: il essaye de prendre la premiere personne disponible... ce qui semble causer des probleme.
Quand j'essaye de faire la répartition a la main, ce n'etait pas comme cela que je faisais.
Il faut en fait s'imaginer une matrice et pour chaque itération, on fait un déplacement par colonne.
Et j'ai pu faire ma répartition de 25 personnes dans des groupes de 5 super facilement.
Je vais prendre l'Exemple de 16 personnes dans 4 groupes de 4 (donc matrice de 4x4)
Ici on a notre répartition de départ (j'utilise A,B,C et D pour que ce soit plus simple): [A1, A2, A3, A4]
[B1, B2, B3, B4]
[C1, C2, C3, C4]
[D1, D2, D3, D4]
La 2e itération est logiquement la même matrice avec une rotation de 90 degré=
[A1, B1, C1, D1]
[A2, B2, C2, D2]
[A3, B3, C3, D3]
[A4, B4, C4, D4]
A partir de celle-ci et pour les itérations suivantes, A sera toujours dans la 1ere column, B dans la 2e, C dans la 3e et D dans la 4e.
A partir de maintenant, il faut prendre l'itération précédente et faire une rotation vers le haut de I pour chaque colonne, I corrrespondant a l'indice de la colonne (en base 0)=
colonne des A (indice 0): pas de déplacement
colonne des B (indice 1): un déplacement vers le haut
colonne des C: deux déplacement vers le haut
colonne des D: trois déplacement vers le haut
Ce qui donne pour l'itération 3:
[A1, B2, C3, D4]
[A2, B3, C4, D1]
[A3, B4, C1, D2]
[A4, B1, C2, D3]
EDIT: je laisse ce message la... mais je viens de me rendre compte que cela marche pas avec une matrice pair ahah.
Mais si vous faites l'Exercice avec une matrice de 5 par 5, ca fonctionne parfaitement: une fois la 1ere ligne faite, pour les lignes suivantes, il faut juste faire +1 par rapport à la ligne précédente.
Je pense que cela fonctionne pour toute matrice de taille N = impair.
Pour les matrice de taille pair, je pense qu'il y a une permutation a faire également mais différente.
Dans tous les cas, cela ne résoud pas le cas ou la matrice n'est pas carré... ou peut-être que si mais aec un nombre max d'itérations différentes.
Je reste persuadé qu'en pensant le probleme en terme de matrice, on peut faire de quoi.
Bel effort! ... Est-ce que le C# ressemble plus à C++ qu'à Python? Peux-tu préciser un peu plus ce que tu fais? 1ière itération: c'est évident. 2ième itération: rotation de 90° = symétrique par rapport à la diagonale principale. 3ième itération: je remonte vers le haut les éléments d'une colonne de i positions, si i est le numéro de la colonne (0 à N-1) (remontée circulaire, le haut s'en va en bas) 4ième itération: c'est là que je ne saisis pas ... Dois-je recommencer la 3ième itération telle quelle? Pour k=5 et N=25, on devrait avoir 6 itérations.
Le Tout est souvent plus grand que la somme de ses parties.
Je connais pas trop la syntaxe du Python mais le c# doit ressembler plus a lui qu'a C++.
mais j'ai pas coder ce que j'ai dis car c'est pas viable pour toutes dimensions
C'est juste mes tests a la main.
Mon code actuel qui va chercher le premier element disponible fonctionne avec une matrice de 3 et 4... a 5 il trouve que 3 itérations alors que je peux en faire 6 a la main (avec l'histoire que j'Ai expliqué)
Pour ta question, oui sur la 4e itération, on fait la même chose en prenant pour départ la répartition de l'itération 3
Ma réflexion sur la matrice de 5 fonctionnait car 5 est un nombre premier (c'est pareil pour 3 et 7).. mais a 9, cela aurait pu fonctionner.
Car mes rotations vers le haut de 1, 2,3 ou 4 élements, je retombais jamais sur le même avant les 5 rotation. Cela ne fonctionne pas avec 4 car ma rotation de 2 retombe sur les mêmes nombre tout le temps
J'Ai remarqué que sur une matrice de 4, il y a avait toujours ce pattern de +1 ou -1 entre chaque groupe/colonne.
Group 1: A1 B2 C3 D4
Group 2: A2 B1 C4 D3
Group 3: A3 B4 C1 D2
Group 4: A4 B3 C2 D1
A +1 pour chaque ligne, B-1 pour chaque ligne, C+1 et D-1
J'Ai essayais de suivre une logique pareil pour une matice de 6 mais cela semble pas fonctionner.
Mon code fait pas de traceback sur les itérations déja passées... mais l'exemple de la matrice 5 le montre: en prenant toujours la plus petit disponible, on trouve que 3 itérations... avec le pattern sur la matrice, on tombe sur les 6 maximum possible.
Quand le nombre de groupes est supérieur au carré (genre 20/4), le code semble pris dans une récursion infinie mais je n'arrive vraiment pas à détecter le pattern. En fait 20/4 il résoud en presque 1 minutes. J'ai peut-être pas pris la bonne approche pour le traceback.
Je réfléchi a ne plus utiliser de backtracking mais plutôt de tester toute les possibilités avec la contrainte suivante:
On se base uniquement sur la 1ere ligne et le 1er element de cette ligne est toujours 0 (A1). La 1ere itération est faite avant.
Je teste toutes les possibilités et je conserve celle qui me donne le plus d'itérations.
Je prend note de ton code et tes remarques. De mon côté, j'ai fait le petit programme Python suivant: (j'ai tout précédé avec des '#*' car mon éditeur me fait perdre l'indentation) L'explication est dans le code. #*""" Répartition d'un sous-ensemble sans répétition. #*On répartit un ensemble de N individus en groupes de k personnes, donc N est divisible par k. #*De sorte qu'à chaque itération de la répartition, personne ne connaît déjà les membres du nouveau groupe. #*Je me met à la place de n'importe quelle personne de l'ensemble. #*Avant la 1ière itération, je ne connais aucune autre personne, donc 0 * (k-1) en tout. #*Après la 1ière itération, je connais k-1 nouvelles personnes, donc 1 * (k-1) en tout. #*Après la 2ième itération, je connais k-1 nouvelles personnes, donc 2 * (k-1) en tout. #*Après la 3ième itération, je connais k-1 nouvelles personnes, donc 3 * (k-1) en tout. #*... #*Après la Xième itération, je connais k-1 nouvelles personnes, donc X * (k-1) en tout. #*Je dois rencontrer exactement k-1 nouvelles personnes à chaque itération, sinon les groupes ne seraient pas complets, ou je vais contre l'hypothèse de départ. #*À la fin, je connais toutes les autres personnes, soient N-1 personnes si je m'exclus. #*Il est donc nécessaire que X soit entier, donc que N-1 soit divisible par k-1. #*Mais j'avais posé que N devait être divisible par k. #*Pour qu'il existe une solution, il faut que N % k == 0 et (N-1) % (k-1) == 0. #*On peut remarquer que si X vaut (k+1), j'aurai (k+1)*(k-1) = N-1, d'ou k²-1 = N-1, et k² = N. #*Mais ce n'est pas une condition nécessaire. #*Le code suivant trouve toutes les possibilités jusqu'à N=100 (j'exclus le cas trivial où k=1) #*Et k=6 (ou 7) et N=42 ne fait pas partie de cette liste. #*""" #*Liste=[] #*Max=100 #*for N in range(2,Max+1): #* for k in range(2,N): #* if N%k==0 and (N-1)%(k-1)==0: Liste.append((k,N)) #*Liste.sort() #*print(*Liste)
Le Tout est souvent plus grand que la somme de ses parties.
Je n'ai toujours pas réglé complètement mon problème de backtracking, mais j'ai une piste de solution. Le programme part en boucle infinie dans certains cas comme N=25 et k=5 On m'a déjà dit que j'étais entêté )à tort ou à raison ...) J'ai écrit du code pour vérifier automatiquement mes solutions. Mon code marche pour N=4|k=2, N=6|k=2, N=8|k=2, N=9|k=3 Si je réussis à faire fonctionner mon code, je pourrais tester toutes les possibilités que j'évoque dans mon message précédent. Je pourrais déjà tester si le nombre d'itération est conforme à la formule (N-1)/(k-1)
Le Tout est souvent plus grand que la somme de ses parties.
J'Ai pas compris totalement ce que faisais ton code.
je n'ai pas repris mon investigation pour ma part.. j'avais besoin de prendre une pause, ca me stressait trop de pas trop de solutions ahah.
Pour la formule (N-1)/(k-1) (avec une matrice carré ou N = k*k).
On est d'Accord que la 1ere itération ne pose pas de difficulté et permet d'Avoir la séparation entre groupe.
La 2e itération est simple également, pour chaque ligne i, on prend l'élément i de chaque groupe (1ere itération)
Pour les itérations suivantes, il faudrait calculer le nombre possibilité (permutation) possible sur la 1ere ligne en fixant que A1 est toujours le 1er élément.
Prenons N=25, k=5 et notons A1..5, B1..5 .... E1..5 chaque personne aprés la 1ere répartition.
la 2e itération, c'est A1 B1 C1 D1 E1 (tout les 2 ensemble, tout les 3, etc.)
Donc a partir de maintenant:
3e itérations:
1er groupe, après A1, il peut y avoir B2,B3,B4 ou B5 en second élément (soit 4 possibilité). En 3e élément, il n'y a pas 4 possibilité mais 3 (car Bx a déjà vu Cx). Après A, B et C fixé, il ne reste que deux possibilité: Dy/Ez ou Dz/Ey
Donc il y a 4*3*2*1 possibilité= 24 permutations possibles: (k-1)! .
Pour le 2e groupe, après A2, il peut y avoir au max 4 possibilités pour B: B1, B3, B4, B5 (en supposant que B2 était choisi pour la 1er groupe). Ensuite pour C: C1, C3, C4, C5 .. mais si B2 à été choisi dans la 1er groupe, alors un de ses 4 éléments était lui aussi dans le 1er groupe. etc.
Le point ou je veux en venir: mon code ne tenait absolument pas compte de cela... j'Avoue que je fais un brute test pour chaque élément à peu de chose près. Donc je pourrais arrêter les récursions bien plus tôt.. Je vais voir pour programmer cela.
Mes maths sont loin, mais combien y a t-il de possibilité de permutations possible pour avoir une itération complete?
Et même si k*k < N, on a g, le nombre de groupes total.
N=15,k=3,g=5
On a A1, A2, A3 jusqu'a E1, E2, E3
A1, A2 et A3 sont toujours repartis dans les trois premiers groupes. Puis en 2e élément, cela peut être B..D, en dernier C..E
les deux derniers groupes, il peut n'y avoir en premier élément B1.. C3, en 2e élément C1..D3 et en dernier élément D1..E3.
Là aussi, on pourrait transposer cela en math dans le programme.
Maintenant, pour chaque permutation possible dans la seconde itération, il faut conserver toutes les possibilités d'itération complète et à la fin, afficher celle qui aura donné le plus d'itérations (ou la premier à respecter la formule (N-1)/(k-1) )
Il doit y avoir une formule également pour une matrice non carré mais je ne l'ai pas encore trouvé
Essentiellement, ce que fait mon code est de vérifier pour N de 2 à Max (ici 100) et k de 2 à N-1: que N est divisible par k, et (N-1) est divisible par (k-1) simultanément. Le append() les met dans une liste que je trie suivant k puis N. Et j'affiche la liste. Pour N=8 et k=2, soit-disant vérifié ... 1 [0, 1] [2, 3] [4, 5] [6, 7] 2 [0, 2] [1, 3] [4, 6] [5, 7] 3 [0, 3] [1, 2] [4, 7] [5, 6] 4 [0, 4] [1, 5] [2, 6] [3, 7] 5 [0, 5] [1, 4] [2, 7] [3, 6] 6 [0, 6] [1, 7] [2, 4] [3, 5] 7 [0, 7] [1, 6] [2, 5] [3, 4] Et (8-1) / (2-1) = 7 Je voulais éviter de jouer avec les permutations car ça monte très vite. Théoriquement, le nombre de façons de permuter 25 éléments est 25!. C'est un nombre astronomiqque. Tu fais des permutations par rottations successives Je n'utilise pas une matrice pour mon algorithme, mais un simple tableau. Les posietions 0 à k-1 forment le 1ier groupe, k à 2k-1 forment le 2ème groupe, etc. C'est moins évident pour moi de faire des rotations par colonnes et vérifier la validité ensuite. Je vais voir ce que je peux faire. En Python, une rotation par ligne se fait ttrès facilement: M[l]=[M[l][(l+i)%N] for i in range(N)] ...
Le Tout est souvent plus grand que la somme de ses parties.
J'ai eu un problème avec mon ordi. Je ne pouvais plus aller sur Internet. Je dois me contenter du Wi-Fi pour le moment. Pendant ce temps, j'ai essayé de coder la méthode avec les matrices carrées, mais en fonctionnant toujours en tableau. Cela me permet d'utiliser ma fonction de validation, et celle d'affichage. Je pense que ma fonction de validation est correcte car si j'introduit une erreur volontaire, elle la détecte. Si la matrice n'est pas carrée comme pour N=8 et k=2, je passe d'une matrice 4 x 2 à 2 x 4, et les permutations deviennent inutiles. J'ai fait plusieurs tests pour mon code avec backtracking et je pense qu'il fonctionne si je considère seulement une itération. Tout me porte à croire que si le programme a fait un mauvais choix dans une itération précédente, cela a un effet sur l'itération courante. Il faudrait donc prolonger le backtracking au dela de l'itération courante. Et ce n'est pas une mince affaire ...
Le Tout est souvent plus grand que la somme de ses parties.
j'ai pas posté de nouvelles ici car j'ai un peu laché l'affaire... :s
PAr ailleurs, on m'a donné plus d'infos sur le problème en question:
c'Est conuu dans la littérature et c'est ce qu'on appelle un block design, plus précisément un (near-) resolvable balanced incomplete block design (ou BIBD en abrégé)
Il y a un bon livre sur le sujet: Handbook of Combinatorial Designs Second Edition, Charles J. Colbourn & Jeffrey H. Dinitz.
mon niveau de math est loin d'être suffisant :/
En gros, ce que je veux résoudre, c'est: RBIBD(N,k,1)
En relisant le topic, c'Est WhiteCrow qui m'a répondu sur un forum ahah.
Mais son idée est celle qui semble à utiliser: utilisation de graphe avec deux «boucles», une pour construire les groupes et une pour construire les itérations.
@PierrotLeFou : en Python, c'est plus facile de gérer des graphes... si le problème te tente toujours
Pour mon cas concret de n=42 et k=6, je fais ca sur un google sheet comme je peux. J'Ai 4 itérations... la 5e avec un minimum de déja vu. Je veux faire que 6e itérations donc ca ira
Par contre, je serais intéressé de connaitre la répartition pour avoir un nombre d'itération parfaite avec N=36 et k=6
Salut, Moi aussi, j'ai un peu mis ça de côté pour l'instant. Je viens tout juste de tester mes deux codes (avec backtracking et par matrices), et aucune ne me donne une bonne solution pour N=36 et k=6. Il y a peut-être un autre truc tordu qui me permettrait de le faire ... Pour N=42 et k=6, je pourrais alléger mes contraintes comme j'avais mentionné au début. Je vais essayer de regarder la documentation que tu donnes. Même si mes math sont parfois un peu loin, je pourrai sans doute trouver quelque chose. Pour les graphes en Python, il y a plus d'une façon de le faire. Je vais regarder ce qui semble le plus facile. Après, je regarderai l'efficacité. Voici tout de même ma solution pour N=36 et k=6 avec la méthode des matrices. Le code détecte des erreurs dans les itérations 4 à 7: 1 [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] 2 [0, 6, 12, 18, 24, 30] [1, 7, 13, 19, 25, 31] [2, 8, 14, 20, 26, 32] [3, 9, 15, 21, 27, 33] [4, 10, 16, 22, 28, 34] [5, 11, 17, 23, 29, 35] 3 [0, 7, 14, 21, 28, 35] [1, 8, 15, 22, 29, 30] [2, 9, 16, 23, 24, 31] [3, 10, 17, 18, 25, 32] [4, 11, 12, 19, 26, 33] [5, 6, 13, 20, 27, 34] 4 [0, 8, 16, 18, 26, 34] [1, 9, 17, 19, 27, 35] [2, 10, 12, 20, 28, 30] [3, 11, 13, 21, 29, 31] [4, 6, 14, 22, 24, 32] [5, 7, 15, 23, 25, 33] 5 [0, 9, 12, 21, 24, 33] [1, 10, 13, 22, 25, 34] [2, 11, 14, 23, 26, 35] [3, 6, 15, 18, 27, 30] [4, 7, 16, 19, 28, 31] [5, 8, 17, 20, 29, 32] 6 [0, 10, 14, 18, 28, 32] [1, 11, 15, 19, 29, 33] [2, 6, 16, 20, 24, 34] [3, 7, 17, 21, 25, 35] [4, 8, 12, 22, 26, 30] [5, 9, 13, 23, 27, 31] 7 [0, 11, 16, 21, 26, 31] [1, 6, 17, 22, 27, 32] [2, 7, 12, 23, 28, 33] [3, 8, 13, 18, 29, 34] [4, 9, 14, 19, 24, 35] [5, 10, 15, 20, 25, 30] La méthode avec backtracking ne donne que 3 solutions au lieu de 7.
Le Tout est souvent plus grand que la somme de ses parties.
Je reprend le message de White Crow (du moins, pour l'essentiel): > je me dirigerai sans doute vers une solution à base de parcours graphe J'ai choisi un dictionnaire de "set()". Les noeuds sortants d'un noeud donné sont dans son set. > Dans ce graphe non dirigé chaque sommet représentera une personne, deux sommets sont reliés par une arrête uniquement si elles n'ont jamais été dans un même groupe. Cela implique qu'on a un lien dans les deux sens: JE ne TE connais pas et TU ne ME connais pas. Chacun des deux voisin est dans le set de l'autre. > Ensuite l'idée de l'algo est relativement simple : Pas si évident que ça ... > pour chaque sommet s du graphe G qui n'est pas marqué D'abord pour chaque itération. > créer un groupe avec s et (n-1) de ses voisins C'est llà que ça se gâte, il faut que chaque élément ne soit pas déjà dans le groupe. Il faut ensuite que chaque éélément soit connecté aux autres membres du groupe. À cause de la symétrie, il suffit que chaque élément déjà dans le groupe soit dans le set du nouveau. > marquer tous les sommets du groupe Facile. Je place chaque élément dans son propre set. > effacer les arrêtes reliant deux sommets quelconques du groupe Enlever chaque élément du set de chacun des autres (deux boucles imbriquées). > Il faut évidemment réinitialiser les marques avant chaque application de l'algo, dans lequel G est ledit graphe et n la taille des groupes. Ça se fait à la fin de l'itération après le dernier groupe complété. Chaque élément ne fait plus partie de son propre set. > Edit: en y réfléchissant plus, mon algo n'est pas correct. En effet il faut également que chacun des voisins choisis soit en relation avec les autres … C'est ce que je voulais dire en disant qu'ils devaient être connectés. Le graphe est en soi un moyen de faire du backtracking. On choisit le noeud suivant dans la liste des noeuds sortants du noeud en qquestion. Mais que se passe-t-il si aucun des noeuds sortants ne satisfait les conditions? Il faut reculer dans le groupe en reconnectant ce qu'on a déconnecté pour ce groupe. Et il faut choisir le noeud suivant (après le prochain élément du groupe( dans la liste des noeuds sortants à chaque étape. (par exemple, si j'ai 3 suivi de 5, il faut que je cherche dans le set de 3 ses noeuds sortants après le 5 ) J'avais pensé de choisir au hasard le noeud sortant pour donner une chance de réussite, mais on ne peut plus faire de backtracking. En théorie, on devrait pouvoir trouver toutes les solutions. Mais il faudra sans doute reculer dans le groupe précédent, voire dans l'itération précédente. Chaque "mauvaise" décision prise dans une itération se reflète dans les suivantes.
Le Tout est souvent plus grand que la somme de ses parties.
Edit : attention, je me suis fourvoyé dans la suite, j'avais mal compris l'énoncé ; la "solution" suivante correspond au problème suivant : créer le maximum de partitions de \(\{1,...,N\}\) en sous-ensembles à k éléments (où k divise N) avec la contrainte suivante : les sous-ensembles doivent être tous différents (ce qui est une contrainte moins forte que celle voulue par Flolem)
J'ai déjà eu affaire au problème que tu soulèves Flolem et j'avoue qu'à part le cas N pair et k=2 (je peux vous proposer une très "jolie" façon de faire dans ce cas), je n'ai pas été capable, par moi-même, de produire un algorithme exhaustif : j'avais besoin d'un tel algo pour des besoins perso mais pas forcément celui exhaustif donc à l'époque, j'avais "simplement" fais un algo où je tirais aléatoirement des sous-ensembles à k éléments de manière "intelligente" pour former le maximum de partitions possibles et en revenant un nombre fixé de fois en arrière sur les derniers choix si ça bloquait à un moment; je m'arrêtais si ce nombre fixé était atteint. Pour N=15 et k=3 je tombais des fois pas loin du nombre maxi de partitions et ça me suffisait.
Bref, ça suffisait mais ce n'était pas du tout satisfaisant !!! Donc j'ai poussé un peu mes recherches, et comme d'habitude, stackoverflow avait la réponse :
En gros, pour les non-angliscites, voilà ce que dit la première réponse, pour ce problème vu côté Maths, le théorème de Baranyai dit qu'on peut trouver une solution : Pour N divisible par k, il existe \(\binom{N-1}{k-1}\) partitions de \(\{1,...,N\}\) composées de sous-ensembles TOUS différents à k éléments (c'est une autre façon de dire qu'il y a un 1 facteur dans l'hypergraphe complet à N sommets et d'hyperaretes reliant toujours k sommets) - on remarque au passage que le nombre de sous-ensembles parcourus est égal à \(\frac{N}{k}\binom{N-1}{k-1}=\binom{N}{k}\) et donc exactement le nombre total de sous-ensembles à k éléments.
Donc dans une solution, on doit placer tous les sous-ensembles à k éléments possibles (d'où la grande difficulté je pense !)
Pour le côté informatique, on peut utiliser un algorithme de flot maximum pour faire les choix de placement des nombres dans les sous-ensembles des partitions.
Dans le post, il y a une implémentation en Python que je n'ai pas testée; mais j'ai codé la mienne (en Python aussi) avec de l'algo de Dinic pour le flot maximum - que je peux partager en MP si ça intéresse quelqu'un qui n'aura pas trop peur de lire du code de Matheux. Ça tourne comme un charme
@sylpro : c'est cool mais ça ne correspond à la construction de tous les tours possibles, il faut ensuite choisir parmi ces tours lesquels peuvent former un championnat. C'est en soi un problème NP difficile. Par exemple il n'existe pas de solution pour N=36 et k=6, mais il y a plusieurs solution pour N=25 et k=5 comme :
Ah oui, au temps pour moi, effectivement, j'avais mal interprété le "avec des nouvelles personnes" du post initial : j'avais compris la contrainte "avec au moins un personne différente" - sûrement parce que j'avais réfléchi à ce cas là justement !
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.