Discussion :

[Bram van Dam]

Bonjour,

Il y a quelques jours ma mère, qui est enseignante, a eu à résoudre un problème d'apparence anodine:
Elle avait une classe de douze élèves dont chacun devait tenir un entretien en tête-à-tête avec chaque autre élève.
Elle comptaient en plus tout organiser onze séances, chacune de ses séances comptant six entretiens.

Ce problème n'est pas aussi facile à résoudre qu'il en a l'air. Elle a commencé elle-même à essayer d'établir un emploi du temps, mais même au bout de deux heures elle n'y est pas parvenu.

On pourrait en tirer la formulation mathématique que voici:

Soit S := {1, 2, ..., 2n} un ensemble de taille paire.
Donner 2n-1 partitions de S tel que tout sous-ensemble de taille deux de S est présent dans une et une seule partition.

J'ai fini par trouver une solution (absolument dégueulasse) dans le cas particulier où 2n = 12: j'ai dressé une liste de toutes les partitions en paires de S, et j'en ai extrait celles dont j'ai besoin pour résoudre le problème dans le cas ou 2n = 6. Avec une astuce, je suis ensuite passé au cas 2n = 12.

Voici maintenant ce que je vous demande: connaissez-vous une façon plus jolie de résoudre le problème ? Je dirais qu'il devrait y avoir un algorithme, qui implique peut-être les facteurs premiers de n, permettant de donner les partitions voulues, peut-être même dans un cas encore plus général.
Est-ce que vous en connaissez un tel algorithme, ou auriez-vous d'autres choses à dire qui valent la peine d'être connues ?

[Flodelarab]

Bonjour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
64
65
66
67
68
69
70
71
72
73
74
75
76
Element1 - e12
Element2 - e11
e03 - e10
e04 - e09
e05 - e08
e06 - e07
 
Element1 - e11
e12 - e10
Element2 - e09
e03 - e08
e04 - e07
e05 - e06
 
Element1 - e10
e11 - e09
e12 - e08
Element2 - e07
e03 - e06
e04 - e05
 
Element1 - e09
e10 - e08
e11 - e07
e12 - e06
Element2 - e05
e03 - e04
 
Element1 - e08
e09 - e07
e10 - e06
e11 - e05
e12 - e04
Element2 - e03
 
Element1 - e07
e08 - e06
e09 - e05
e10 - e04
e11 - e03
e12 - Element2
 
Element1 - e06
e07 - e05
e08 - e04
e09 - e03
e10 - Element2
e11 - e12
 
Element1 - e05
e06 - e04
e07 - e03
e08 - Element2
e09 - e12
e10 - e11
 
Element1 - e04
e05 - e03
e06 - Element2
e07 - e12
e08 - e11
e09 - e10
 
Element1 - e03
e04 - Element2
e05 - e12
e06 - e11
e07 - e10
e08 - e09
 
Element1 - Element2
e03 - e12
e04 - e11
e05 - e10
e06 - e09
e07 - e08

1. Tu écris le premier tour.
2. Tu fixes une équipe.
3. Tu fais tourner toutes les autres équipes d'un cran.
4. Quand tu es revenu au point de départ, c'est que tu as fait tous les cas possibles. FIN
5. Sinon tu retournes à l'étape 3.

[anapurna]

salut

avant de donnée les partition il te faut calculer les combinaison
pour trouver le nombre de possibilité la formule est =FACTORIELLE(n)/((FACTORIELLE(2)*FACTORIELLE(n-2)))

le calcul de factoriel est FACT(N) =1*2*3*..*N
exemple FACT(10) = 3 628 800

la représentation graphique peut être fait a l'aide d'un tableau a double entrée
les n chiffre en ordonne et en abscisse

exemple avec 4 éléments pour simplifier

1 2 3 4
2 3 4
3 4
4

donc le nombre de paire possible
est 1-2 1-3 1-4 , 2-3 2-4 et 3-4

une simple implication de deux boucle te permet de définir tout tes couples possible

une fois les couples obtenu il te faut refaire
une double boucle afin de sélectionner les couple pouvant participer au différent tour
dans l'exemple de quatre

le premier tour seras
1-2 et 3-4
le second
1-3 et 2-4
le troisième
1-4 et 2-3

mes 2 cts

[Bram van Dam]

Merci pour vos réponses,

@Flodelarab, pour comprendre ce que tu veux dire par
"faire tourner toutes les équipes d'un cran."
je devrais avoir le petit dessin à l'esprit auquel tu penses.
Je ne comprends pas tellement non plus ce que tu veux dire par "fixer une équipe".
Cela voudrait-il dire qu'il faut mettre une équipe de côté pour faire une espèce de décalage circulaire répété avec les équipes restantes?
Sinon l'organisation que tu as mise au début de ta réponse m'a l'air bien, même si je ne vois pas vraiment la fonction de Element1 et 2 là-dedans.
Ces sont deux équipes qu'on devrait également faire jouer un match ensemble, n'est-ce pas ?

@anapurna, Je ne sais pas sûr de bien comprendre dans quel ordre le sélectionnement de couples devrait se dérouler
dans cette boucle double dont tu parles. Ce que je peux dire en revanche,
c'est que le "remplissage" séparé de chacun des tours pourrait coincer:

si on se met à créer des listes de couples une par une sans ce soucier des tours à venir,
on pourrait finir par se retrouver avec une n-ième liste qui ne peut contenir que quatre couples
sans ajouter un couple déjà ajouté dans une des autres listes.
C'était la méthode que mon père a essayée, et elle a échouée.

Merci d'avance de m'aider.

[Flodelarab]

même si je ne vois pas vraiment la fonction de Element1 et 2 là-dedans.

Ce ne sont pas des fonctions. Les deux premiers éléments s'appellent comme ça, puis, avec la flemme, j'ai appelé les suivants e3 e4 e5 ...

Cela voudrait-il dire qu'il faut mettre une équipe de côté pour faire une espèce de décalage circulaire répété avec les équipes restantes?

C'est exactement cela.
Regarde. "Élément 1" ne bouge jamais. Et les autres permutent. Vérifie-le en remarquant que la position suivant la dernière position aurait dû être la première position.

Ces sont deux équipes qu'on devrait également faire jouer un match ensemble, n'est-ce pas ?

Chaque ligne est un match.
Chaque journée est séparée par une ligne vide.

[tbc92]

Si 1 ne bouge pas, et que les autres 'permutent' , j'ai l'impression que 3 et 4 vont se rencontrer à tous les tours impairs.

Je propose ce mouvement :
Chaque table a 2 chaises : Nord et Sud.
Partons sur 6 tables. Les n° impairs sont en Nord, et les n° pairs sont en sud.
Dans un premier temps, ceux qui sont en Nord ne bougent pas. Et ceux qui sont en sud montent d'un cran à chaque position. Cette base reste valable tant qu'on a un nombre de personnes qui est un multiple de 4.
On a donc 6 positions, et tous les Nords(les impairs) ont rencontré tous les Suds(les pairs).
Maintenant, il faut trouver comment gérer les 5 dernières positions. On a 6 impairs (1 3 5 7 9 11) qui doivent se rencontrer 2 à 2 (et on dupliquera le mouvement trouvé pour les n° pairs)
exemple :
1,3 5,7 9,11
1,5 7,9 11,3
1,7 9,3 3,11
1,9 11,7 3,5
1,11 3,7 5,9

[Flodelarab]

Si 1 ne bouge pas, et que les autres 'permutent' , j'ai l'impression que 3 et 4 vont se rencontrer à tous les tours impairs.

Mais j'ai donné le résultat complet.
Tu vois bien que 3 et 4 se rencontrent en jour 4 et pas autrement.
C'est le mot "permutent" qui dérange ? Alors je change : les autres coulissent.

[tbc92]

Désolé, je n'avais pas vu 'permutent' comme ça.

[anapurna]

salut

je ne suis pas sure que cela soit réalisable sans répétition

même si nous avons 66 combinaison possible pour 12 couples

il ne me parait pas possible de définir 11 couple dans 6 groupe sachant que pour chaque personne il y a 11 permutation possible

mais 11 groupe de 6 couple sans répétition cela me parait faisable

et voici une répartition possible pour 11 groupe

[Nebulix]

Flodelarab a donné la bonne solution. Elle peut être visualisée comme un mouvement de chenille de char :

1 2 3 4 5 6 C 1 2 3 4 5 B C 1 2 3 4
C B A 9 8 7 > B A 9 8 7 6 > A 9 8 7 6 5

[anapurna]

salut

arf oui bin on a la même solution
j'avais mal lu je pensais qu'il voulais 11 couples dans 6 groupe (faut que j’arrête de lire de biais ou alors l'alcool )

si tu regarde mes grilles je montre une des solutions trouvé avec 6 couples et 12 personnes

j'utilise la somme pour savoir si mon résultat de 6 couple est cohérent
imaginons que tu ais 12 élèves tu leur attribue un rang
1,2,...12
la somme des rangs est donc 1+2+...+12 = 78

c'est cette somme me permet de vérifier mes permutations

En fait tout ceci se rapproche beaucoup de la résolution d'un sudoku
il y a une multitude de possibilité pour avoir le résultat

PS si l'on regarde bien les images on distingue bien un axe ainsi que la distribution de 3 couples de chaque cotés

[JeitEmgie]

Données de départ

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
Elèves :
1 -> [2,3,4,5,6,7,8,9,10,11,12]
2 -> [1,3,4,5,6,7,8,9,10,11,12]
3 -> [1,2,4,5,6,7,8,9,10,11,12]
4 -> [1,2,3,5,6,7,8,9,10,11,12]
5 -> [1,2,3,4,6,7,8,9,10,11,12]
6 -> [1,2,3,4,5,7,8,9,10,11,12]
7 -> [1,2,3,4,5,6,8,9,10,11,12]
8 -> [1,2,3,4,5,6,7,9,10,11,12]
9 -> [1,2,3,4,5,6,7,8,10,11,12]
10 -> [1,2,3,4,5,6,7,8,9,11,12]
11 -> [1,2,3,4,5,6,7,8,9,10,12]
12 -> [1,2,3,4,5,6,7,8,9,10,11]
 
 
Séances :
S[1,2,3,...,11] ->[]

Constituer une séance :
constituer une paire :
prendre dans le premier élève non vide non encore utilisé dans la séance en cours, le premier élément non encore utilisé dans la séance en cours
prendre dans l'élève suivant le précédent et non vide, le premier élément non encore utilisé dans la séance en cours
si la paire n'est pas encore utilisée dans les séances précédentes on la garde
sinon on passe à la possibilité suivante, si pas de possibilité suivante : on backtrack à l'étape précédente
mettre à jour la structure


Séance 1
premier non vide = 1
premier non utilisé = 2
-> (1,2)
premier non vide non utilisé = 3
premier non utilisé = 4
-> (3,4)
...


À la fin S[1] = [ (1,2), (3,4), (5,6), (7,8), (9,10), (11,12) ]


Structure mise à jour :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
Elèves :
1 -> [3,4,5,6,7,8,9,10,11,12]
2 -> [3,4,5,6,7,8,9,10,11,12]
3 -> [1,2,5,6,7,8,9,10,11,12]
4 -> [1,2,5,6,7,8,9,10,11,12]
5 -> [1,2,3,4,7,8,9,10,11,12]
6 -> [1,2,3,4,7,8,9,10,11,12]
7 -> [1,2,3,4,5,6,9,10,11,12]
8 -> [1,2,3,4,5,6,9,10,11,12]
9 -> [1,2,3,4,5,6,7,8,11,12]
10 -> [1,2,3,4,5,6,7,8,11,12]
11 -> [1,2,3,4,5,6,7,8,9,10]
12 -> [1,2,3,4,5,6,7,8,9,10]
 
 
Séances :
S[1] -> [ (1,2), (3,4), (5,6), (7,8), (9,10), (11,12) ]
S[2,3,...,11] ->[]

Séance 2
(1,3), (2,4), (5,7), (6,8), (9,11),(10,12)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
Elèves :
1 -> [4,5,6,7,8,9,10,11,12]
2 -> [3,5,6,7,8,9,10,11,12]
3 -> [2,5,6,7,8,9,10,11,12]
4 -> [1,5,6,7,8,9,10,11,12]
5 -> [1,2,3,4,8,9,10,11,12]
6 -> [1,2,3,4,7,9,10,11,12]
7 -> [1,2,3,4,6,9,10,11,12]
8 -> [1,2,3,4,5,9,10,11,12]
9 -> [1,2,3,4,5,6,7,8,12]
10 -> [1,2,3,4,5,6,7,8,11]
11 -> [1,2,3,4,5,6,7,8,10]
12 -> [1,2,3,4,5,6,7,8,9]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3,...,11] ->[]

Séance 3
(1,4),(2,3),(5,8),(6,7),(9,12)(10,11)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
Elèves :
1 -> [5,6,7,8,9,10,11,12]
2 -> [5,6,7,8,9,10,11,12]
3 -> [5,6,7,8,9,10,11,12]
4 -> [5,6,7,8,9,10,11,12]
5 -> [1,2,3,4,9,10,11,12]
6 -> [1,2,3,4,9,10,11,12]
7 -> [1,2,3,4,9,10,11,12]
8 -> [1,2,3,4,9,10,11,12]
9 -> [1,2,3,4,5,6,7,8]
10 -> [1,2,3,4,5,6,7,8]
11 -> [1,2,3,4,5,6,7,8]
12 -> [1,2,3,4,5,6,7,8]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4,...,11] ->[]

Séance 4
(1,5)(2,6)(3,7)(4,8)
(1,5)(2,6)(3,7)(4,9)(8,10)
(1,5)(2,6)(3,7)(4,9)(8,11)
(1,5)(2,6)(3,7)(4,9)(8,12)
(1,5)(2,6)(3,7)(4,10)(8,9)
(1,5)(2,6)(3,7)(4,10)(8,11)
(1,5)(2,6)(3,7)(4,10)(8,12)
(1,5)(2,6)(3,7)(4,11)(8,9)
(1,5)(2,6)(3,7)(4,11)(8,10)
(1,5)(2,6)(3,7)(4,11)(8,12)
(1,5)(2,6)(3,7)(4,12)(8,9)
(1,5)(2,6)(3,8)(4,9)(7,10)
(1,5)(2,6)(3,8)(4,9)(7,11)
(1,5)(2,6)(3,8)(4,9)(7,12)
(1,5)(2,6)(3,8)(4,10)(7,9)
(1,5)(2,6)(3,8)(4,10)(7,11)
(1,5)(2,6)(3,8)(4,10)(7,12)
(1,5)(2,6)(3,8)(4,11)(7,10)
(1,5)(2,6)(3,8)(4,12)(7,9)
(1,5)(2,6)(3,8)(4,12)(7,11)
(1,5)(2,6)(3,8)(4,12)(7,12)
(1,5)(2,6)(3,9)(4,7)(8,10)
(1,5)(2,6)(3,9)(4,7)(8,11)
(1,5)(2,6)(3,9)(4,7)(8,12)
(1,5)(2,6)(3,9)(4,8)(7,10)
(1,5)(2,6)(3,9)(4,8)(7,11)
(1,5)(2,6)(3,9)(4,8)(7,12)
(1,5)(2,6)(3,9)(4,10)(7,11)
(1,5)(2,6)(3,9)(4,10)(7,12)
(1,5)(2,6)(3,9)(4,11)(7,10)
(1,5)(2,6)(3,9)(4,11)(7,12)
(1,5)(2,6)(3,9)(4,12)(7,10)
(1,5)(2,6)(3,9)(4,12)(7,11)
(1,5)(2,6)(3,10)(4,7)(8,9)
(1,5)(2,6)(3,10)(4,7)(8,11)
(1,5)(2,6)(3,10)(4,7)(8,12)
(1,5)(2,6)(3,10)(4,8)(7,9)
(1,5)(2,6)(3,10)(4,8)(7,11)
(1,5)(2,6)(3,10)(4,8)(7,12)
(1,5)(2,6)(3,10)(4,9)(7,10)
(1,5)(2,6)(3,10)(4,9)(7,11)
(1,5)(2,6)(3,10)(4,9)(7,12)
(1,5)(2,6)(3,10)(4,11)(7,9)(8,12)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
Elèves :
1 -> [6,7,8,9,10,11,12]
2 -> [5,7,8,9,10,11,12]
3 -> [5,6,7,8,9,11,12]
4 -> [5,6,7,8,9,10,12]
5 -> [2,3,4,9,10,11,12]
6 -> [1,3,4,9,10,11,12]
7 -> [1,2,3,4,10,11,12]
8 -> [1,2,3,4,9,10,11]
9 -> [1,2,3,4,5,6,8]
10 -> [1,2,4,5,6,7,8]
11 -> [1,2,3,5,6,7,8]
12 -> [1,2,3,4,5,6,7]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[5,...,11] ->[]

Séance 5
(1,6)(2,5)(3,7)(4,8)(5,9)
(1,6)(2,5)(3,7)(4,8)(5,10)
(1,6)(2,5)(3,7)(4,8)(5,11)
(1,6)(2,5)(3,7)(4,8)(5,12)
(1,6)(2,5)(3,7)(4,9)(8,10)
(1,6)(2,5)(3,7)(4,9)(8,11)
(1,6)(2,5)(3,7)(4,10)(8,9)
(1,6)(2,5)(3,7)(4,10)(8,11)
(1,6)(2,5)(3,7)(4,11)(8,10)
(1,6)(2,5)(3,7)(4,12)(8,9)
(1,6)(2,5)(3,7)(4,12)(8,10)
(1,6)(2,5)(3,7)(4,12)(8,11)
(1,6)(2,5)(3,8)(4,7)
(1,6)(2,5)(3,8)(4,9)(7,10)
(1,6)(2,5)(3,8)(4,9)(7,11)
(1,6)(2,5)(3,8)(4,9)(7,12)
(1,6)(2,5)(3,8)(4,10)(7,11)
(1,6)(2,5)(3,8)(4,10)(7,12)
(1,6)(2,5)(3,8)(4,12)(7,10)
(1,6)(2,5)(3,8)(4,12)(7,11)
(1,6)(2,5)(3,8)(4,12)(7,12)
(1,6)(2,5)(3,9)(4,7)(8,10)
(1,6)(2,5)(3,9)(4,7)(8,11)
(1,6)(2,5)(3,9)(4,8)(7,10)
(1,6)(2,5)(3,9)(4,8)(7,11)
(1,6)(2,5)(3,9)(4,8)(7,12)
(1,6)(2,5)(3,9)(4,8)(7,10)
(1,6)(2,5)(3,9)(4,8)(7,11)
(1,6)(2,5)(3,9)(4,8)(7,12)
(1,6)(2,5)(3,9)(4,10)(7,11)
(1,6)(2,5)(3,9)(4,8)(7,12)
(1,6)(2,5)(3,9)(4,10)(7,11)
(1,6)(2,5)(3,9)(4,12)(7,10)(8,11)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
Elèves :
1 -> [7,8,9,10,11,12]
2 -> [7,8,9,10,11,12]
3 -> [5,6,7,8,11,12]
4 -> [5,6,7,8,9,10]
5 -> [3,4,9,10,11,12]
6 -> [3,4,9,10,11,12]
7 -> [1,2,3,4,11,12]
8 -> [1,2,3,4,9,10]
9 -> [1,2,4,5,6,8]
10 -> [1,2,4,5,6,8]
11 -> [1,2,3,5,6,7]
12 -> [1,2,3,5,6,7]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[5] -> [ (1,6),(2,5),(3,9),(4,12),(7,10),(8,11) ]
S[6,...,11] ->[]

Séance 6
(1,7)(2,8)(3,5)(4,6)
(1,7)(2,8)(3,5)(4,9)(6,10)
(1,7)(2,8)(3,5)(4,9)(6,11)
(1,7)(2,8)(3,5)(4,9)(6,12)
(1,7)(2,8)(3,5)(4,10)(6,11)
(1,7)(2,8)(3,5)(4,10)(6,12)
(1,7)(2,8)(3,6)(4,5)
(1,7)(2,8)(3,6)(4,9)(5,10)
(1,7)(2,8)(3,6)(4,9)(5,11)
(1,7)(2,8)(3,6)(4,9)(5,12)
(1,7)(2,8)(3,6)(4,10)(5,11)
(1,7)(2,8)(3,6)(4,10)(5,12)
(1,7)(2,8)(3,11)(4,5)(6,9)
(1,7)(2,8)(3,11)(4,5)(6,10)
(1,7)(2,8)(3,11)(4,5)(6,12)
(1,7)(2,8)(3,11)(4,6)(5,9)
(1,7)(2,8)(3,11)(4,6)(5,10)
(1,7)(2,8)(3,11)(4,6)(5,12)
(1,7)(2,8)(3,11)(4,9)(5,10)
(1,7)(2,8)(3,11)(4,9)(5,12)
(1,7)(2,8)(3,11)(4,10)(5,9)(6,12)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
Elèves :
1 -> [8,9,10,11,12]
2 -> [7,9,10,11,12]
3 -> [5,6,7,8,12]
4 -> [5,6,7,8,9]
5 -> [3,4,10,11,12]
6 -> [3,4,9,10,11]
7 -> [2,3,4,11,12]
8 -> [1,3,4,9,10]
9 -> [1,2,4,6,8]
10 -> [1,2,5,6,8]
11 -> [1,2,5,6,7]
12 -> [1,2,3,5,7]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[5] -> [ (1,6),(2,5),(3,9),(4,12),(7,10),(8,11) ]
S[6] -> [ (1,7),(2,8),(3,11),(4,10),(5,9),(6,12) ]
S[7,...,11] ->[]

Séance 7
(1,8)(2,7)(3,5)(4,9)(6,10)
(1,8)(2,7)(3,5)(4,9)(6,11)
(1,8)(2,7)(3,6)(4,9)(5,10)
(1,8)(2,7)(3,12)(4,5)(6,9)
(1,8)(2,7)(3,12)(4,5)(6,10)
(1,8)(2,7)(3,12)(4,5)(6,11)
(1,8)(2,7)(3,12)(4,6)(5,10)
(1,8)(2,7)(3,12)(4,6)(5,11)
(1,8)(2,7)(3,12)(4,9)(5,10)(6,11)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Elèves :
1 -> [9,10,11,12]
2 -> [9,10,11,12]
3 -> [5,6,7,8]
4 -> [5,6,7,8]
5 -> [3,4,11,12]
6 -> [3,4,9,10]
7 -> [3,4,11,12]
8 -> [3,4,9,10]
9 -> [1,2,6,8]
10 -> [1,2,6,8]
11 -> [1,2,5,7]
12 -> [1,2,5,7]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[5] -> [ (1,6),(2,5),(3,9),(4,12),(7,10),(8,11) ]
S[6] -> [ (1,7),(2,8),(3,11),(4,10),(5,9),(6,12) ]
S[7] -> [ (1,8),(2,7),(3,12),(4,9),(5,10),(6,11) ]
S[8,...,11] ->[]

Séance 8
(1,9)(2,10)(3,5)(4,6)(7,11)
(1,9)(2,10)(3,5)(4,6)(7,12)
(1,9)(2,10)(3,5)(4,7)
(1,9)(2,10)(3,5)(4,8)
(1,9)(2,10)(3,6)(4,5)(7,11)
(1,9)(2,10)(3,6)(4,5)(7,12)
(1,9)(2,10)(3,6)(4,7)(5,11)
(1,9)(2,10)(3,6)(4,7)(5,12)
(1,9)(2,10)(3,6)(4,8)(5,11)(7,12)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Elèves :
1 -> [10,11,12]
2 -> [9,11,12]
3 -> [5,7,8]
4 -> [5,6,7]
5 -> [3,4,12]
6 -> [4,9,10]
7 -> [3,4,11]
8 -> [3,9,10]
9 -> [2,6,8]
10 -> [1,6,8]
11 -> [1,2,7]
12 -> [1,2,5]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[5] -> [ (1,6),(2,5),(3,9),(4,12),(7,10),(8,11) ]
S[6] -> [ (1,7),(2,8),(3,11),(4,10),(5,9),(6,12) ]
S[7] -> [ (1,8),(2,7),(3,12),(4,9),(5,10),(6,11) ]
S[8] -> [ (1,9),(2,10),(3,6),(4,8),(5,11),(7,12) ]
S[9,...,11] ->[]

Séance 9
(1,10)(2,9)(3,5)(4,6)(7,11)
(1,10)(2,9)(3,7)(4,6)(5,12)
(1,10)(2,9)(3,7)(4,7)(5,12)
(1,10)(2,9)(3,8)(4,7)(5,12)
(1,10)(2,11)(3,5)(4,6)
(1,10)(2,11)(3,5)(4,7)(6,9)
(1,10)(2,11)(3,7)(4,5)(6,9)
(1,10)(2,11)(3,7)(4,6)(5,12)(8,9)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Elèves :
1 -> [11,12]
2 -> [9,12]
3 -> [5,8]
4 -> [5,7]
5 -> [3,4]
6 -> [9,10]
7 -> [4,11]
8 -> [3,10]
9 -> [2,6]
10 -> [6,8]
11 -> [1,7]
12 -> [1,2]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[5] -> [ (1,6),(2,5),(3,9),(4,12),(7,10),(8,11) ]
S[6] -> [ (1,7),(2,8),(3,11),(4,10),(5,9),(6,12) ]
S[7] -> [ (1,8),(2,7),(3,12),(4,9),(5,10),(6,11) ]
S[8] -> [ (1,9),(2,10),(3,6),(4,8),(5,11),(7,12) ]
S[9] -> [ (1,10),(2,11),(3,7),(4,6),(5,12),(8,9) ]
S[10,...,11] ->[]

Séance 10
(1,11)(2,9)(3,5)(4,7)(6,10)
(1,11)(2,9)(3,8)(4,5)(6,10)
(1,11)(2,9)(3,8)(4,7)(6,10)
(1,11)(2,12)(3,5)(4,7)(6,9)(8,10)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Elèves :
1 -> [12]
2 -> [9]
3 -> [8]
4 -> [5]
5 -> [4]
6 -> [10]
7 -> [11]
8 -> [3]
9 -> [2]
10 -> [6]
11 -> [7]
12 -> [1]
 
 
Séances :
S[1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[5] -> [ (1,6),(2,5),(3,9),(4,12),(7,10),(8,11) ]
S[6] -> [ (1,7),(2,8),(3,11),(4,10),(5,9),(6,12) ]
S[7] -> [ (1,8),(2,7),(3,12),(4,9),(5,10),(6,11) ]
S[8] -> [ (1,9),(2,10),(3,6),(4,8),(5,11),(7,12) ]
S[9] -> [ (1,10),(2,11),(3,7),(4,6),(5,12),(8,9) ]
S[10] -> [ (1,11),(2,12),(3,5),(4,7),(6,9),(8,10) ]
S[11] ->[]

Séance 11
(1,12)(2,9)(3,8)(4,5)(6,10)(7,11)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Séances :
S[ 1] -> [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
S[ 2] -> [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
S[ 3] -> [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
S[ 4] -> [ (1,5),(2,6),(3,10),(4,11),(7,9),(8,12) ]
S[ 5] -> [ (1,6),(2,5),(3,9),(4,12),(7,10),(8,11) ]
S[ 6] -> [ (1,7),(2,8),(3,11),(4,10),(5,9),(6,12) ]
S[ 7] -> [ (1,8),(2,7),(3,12),(4,9),(5,10),(6,11) ]
S[ 8] -> [ (1,9),(2,10),(3,6),(4,8),(5,11),(7,12) ]
S[ 9] -> [ (1,10),(2,11),(3,7),(4,6),(5,12),(8,9) ]
S[10] -> [ (1,11),(2,12),(3,5),(4,7),(6,9),(8,10) ]
S[11] -> [ (1,12),(2,9),(3,8),(4,5),(6,10),(7,11) ]

[tbc92]

La solution de Flodelarab a un gros avantage, c'est qu'elle est facile à mettre en place.
La prof demande aux 12 élèves de s'asseoir sur les 12 chaises.
Et à chaque changement, elle dit à l'élève n°1 de ne pas bouger, et aux autres 11 élèves de se déplacer d'un cran : L'élève X va prendre la place de l'élève X-1 à chaque changement.
Très facile à mettre en oeuvre, même avec des gamins dissipés.

[anapurna]

salut

avec cette méthode tu ne tiens pas comptes des redondances ?
le couple 3-4 est le même que le couple 4-3
il y a forcement des test supplémentaire de plus je pense qu'il y a optimisation possible
avec le fait que dans la distribution nous avons forcement 3 couples "faible" et 3 couples "Fort"
que la somme des couple doit être égale a la somme des rang des élèves ... pour 12 c'est 78 =1+2+3+4...+12
je suis sur qu'avec tout les mathématicien ici il y en a bien un qui vas trouver une solution

[tbc92]

Dans le scénario de JeitEmgie, quand il cherche à 'caser' l'individu n°4, il a forcément déjà casé les individus n° 1 2 et 3. Il ne va donc jamais générer la rencontre 4-3. Pas de problème avec ça. Sa méthode est longue, mais elle marche.
Contrôler que la somme donne 78, ça n'apporte rien. A partir du moment où tous les enfants sont casés, la somme fait 78. Et on pourrait avoir une somme qui donne 78, avec des enfants casés 2 fois...

La proposition de Flodelarab est parfaite. Elle est simple, et ne nécessite pas de 'Backtracking...'
Cette méthode marche quelque soit le nombre d'élèves (tant qu'il est pair), pas uniquement pour 12 élèves.
Eventuellement, une démonstration 'formelle' que ça marche toujours pourrait être intéressante.

[JeitEmgie]

Dans le scénario de JeitEmgie, quand il cherche à 'caser' l'individu n°4, il a forcément déjà casé les individus n° 1 2 et 3. Il ne va donc jamais générer la rencontre 4-3. Pas de problème avec ça. Sa méthode est longue, mais elle marche.

à la main c'est long, un programme donnera la solution en quelques dizaines de millisecondes (oops...) trop pessimiste: 9ms (pour n=6).

[anapurna]

salut

c'est le tableau de base qui me gène

Elèves :
1 -> [2,3,4,5,6,7,8,9,10,11,12]
2 -> [1,3,4,5,6,7,8,9,10,11,12]
3 -> [1,2,4,5,6,7,8,9,10,11,12]
4 -> [1,2,3,5,6,7,8,9,10,11,12]
5 -> [1,2,3,4,6,7,8,9,10,11,12]
6 -> [1,2,3,4,5,7,8,9,10,11,12]
7 -> [1,2,3,4,5,6,8,9,10,11,12]
8 -> [1,2,3,4,5,6,7,9,10,11,12]
9 -> [1,2,3,4,5,6,7,8,10,11,12]
10 -> [1,2,3,4,5,6,7,8,9,11,12]
11 -> [1,2,3,4,5,6,7,8,9,10,12]
12 -> [1,2,3,4,5,6,7,8,9,10,11]

je l'aurais plutot vu ainsi

Elèves :
1 -> [2,3,4,5,6,7,8,9,10,11,12]
2 -> [ ,3,4,5,6,7,8,9,10,11,12]
3 -> [ , ,4,5,6,7,8,9,10,11,12]
4 -> [ , , ,5,6,7,8,9,10,11,12]
5 -> [ , , , ,6,7,8,9,10,11,12]
6 -> [ , , , , ,7,8,9,10,11,12]
7 -> [ , , , , , ,8,9,10,11,12]
8 -> [ , , , , , , ,9,10,11,12]
9 -> [ , , , , , , , ,10,11,12]
10 -> [ , , , , , , , , ,11,12]
11 -> [ , , , , , , , , , ,12]

ce qui limite les recherches à la moitie du tableau
j'ai volontairement mis les case creuse mais celle-ci sont d'aucune utilité
de se fait on limite considérablement le choix des couples
il y a plein d'autres simplification à faire
par exemple on sais que la fameuse diagonal va de [(M div 2),(N div 2 +1)] a [1,N] avec M=N

ensuite je suppose que l'on doit pouvoir trouver une symétrie par rapport a cette axe
c'est a dire que si tu prend [1,2] tu prend aussi [11,12]
[1,3] " " [10,12]
[1,4] " " [ 9 ,12]
et ainsi de suite

[JeitEmgie]

salut

c'est le tableau de base qui me gène

faites l'exercice à la main, vous verrez bien ce qui se passe avec ces données de base…


















(en fait à la séance 4, vous ne trouverez pas (9,4)… et vous serez coincé…
en activant le debug sur mes données de base:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
1 [ (1,2),(3,4),(5,6),(7,8),(9,10),(11,12) ]
2 [ (1,3),(2,4),(5,7),(6,8),(9,11),(10,12) ]
3 [ (1,4),(2,3),(5,8),(6,7),(9,12),(10,11) ]
debug: inserting inverted mate 9 4
...

avec votre version des données de base cela se termine par
EmptyStackException
lors du backtracking
)

[anapurna]

salut

c'est quand même un peut ce que j'ai fait avec mes image on arrive au meme resultat sauf que je reduit la champs de recherche

après je viens de tester ma méthode ne fonctionne que pour des multiple de 4

si vous prenez 14 qu'elle est le résultat ?

[Flodelarab]

Console Linux (bash):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
$ tab=(2 3 4 5 6 7 8 9 10 11 12)
$ time for ((t=0;t<11;t++));do for ((i=0;i<6;i++)); do if [ $i -eq 0 ];then e1=1; else e1=${tab[t+i-12]}; fi; echo "$e1 - ${tab[t-i-1]}"; done;echo;done
1 - 12
2 - 11
3 - 10
4 - 9
5 - 8
6 - 7
 
1 - 2
3 - 12
4 - 11
5 - 10
6 - 9
7 - 8
 
1 - 3
4 - 2
5 - 12
6 - 11
7 - 10
8 - 9
 
1 - 4
5 - 3
6 - 2
7 - 12
8 - 11
9 - 10
 
1 - 5
6 - 4
7 - 3
8 - 2
9 - 12
10 - 11
 
1 - 6
7 - 5
8 - 4
9 - 3
10 - 2
11 - 12
 
1 - 7
8 - 6
9 - 5
10 - 4
11 - 3
12 - 2
 
1 - 8
9 - 7
10 - 6
11 - 5
12 - 4
2 - 3
 
1 - 9
10 - 8
11 - 7
12 - 6
2 - 5
3 - 4
 
1 - 10
11 - 9
12 - 8
2 - 7
3 - 6
4 - 5
 
1 - 11
12 - 10
2 - 9
3 - 8
4 - 7
5 - 6
 
 
real    0m0,001s
user    0m0,000s
sys     0m0,000s

La variable t représente le tour et la variable i, le match dans le tour.
real est le temps réel mis pour exécuter.
user est le temps utilisateur.
sys est le temps cpu.

1 milliseconde réelle, tout compté.

Je ne comprends pas ce que vous trafiquer avec vos tableaux.