Discussion :

[SCalc]

Bonjour,

j'aurais besoin d'un algorithme permettant de creer m paires uniques de personnes prises parmi n personnes.

Pour être plus précis:

- j'ai n personnes à "marier"
- chaque personne doit être mariée avec p autres personnes (p est pair)
- (donc si je calcule bien, je vais créer n*p / 2 = m paires)
- il ne doit pas y avoir 2 paires identiques
- une personne ne peut pas être mariée avec elle-même
- chaque personne doit être p/2 fois en première position dans une paire, p/2 fois en 2e position

Exemple: si j'ai 4 personnes A, B, C, D et que p vaut 2, je peux (je dois ?) faire:

(A,B), (C,D), (D,A), (B,C)

Bon, je vais réfléchir à la façon de généraliser ça, mais si vous avez une idée...

PS: ce sera codé en php 4

Jérôme

[FrancisSourd]

Si on prend 0, 1, 2, ... n-1 au lieu de A, B, C...

Est-ce que
union_0≤i<n {(i,i+1 mod n),....(i,i+p/2 mod n)}
conviendrait?

Si tu as des préférences sur les paires, tu peux aussi regarder cela comment un problème de flot à coût minimum.

[FR119492]

Salut !

Outre le fait que la polygamie est interdite par la plupart des législations occidentales, je ne vois pas bien l'intérêt de ton problème. Peux-tu préciser?

Jean-Marc Blanc

[SCalc]

Pour Francis: je n'ai rien compris à la formule (désolé, c'est peut-être mon niveau en maths). Est-ce qu'il y a un moyen de la réécrire de façon "moins compacte" ?

Pour Jean-Marc: c'est pour un site de jeu d'échecs en ligne, sur lequel je veux organiser des tournois et où donc il faut "apparier" les joueurs avec les blancs et avec les noirs.

Jérôme

[FrancisSourd]

union_0≤i<n {(i,i+1 mod n),....(i,i+p/2 mod n)}

ex: pour n=7 p=4

i=0 (0,1) (0,2)
i=1 (1,2) (1,3)
i=2 (2,3) (2,4)
i=3 (3,4) (3,5)
i=4 (4,5) (4,6)
i=5 (5,6) (5,7 mod 7)=(5,0)
i=6 (6,7 mod 7) =(6,0) (6,8 mod 7)=(6,1)

J'espère que c'est plus clair! Ce n'est en tout cas pas la seule solution, c'est pour cela que je te parle de cherche une solution optimisée en évoquant des paires préférées.

[SCalc]

Bonjour,

merci, c'est très clair et très simple, ça devrait me suffire.

Jérôme