Création automaique de binômes non-aléatoires
Bonsoir a toutes et à tous et merci par avance pour l'aide que vous pourrez m'apporter.
Je suis amené à devoir constituer des binômes selon les bases et règles suivantes :
- J'ai une base de 50 agents (en ligne dans le fichier joint)
- Chaque agent doit effectuer 5 souhaits d'association avec tel ou tel autre agent (toujours sur le même périmètre d'agents - les souhaits sont en colonne)
- Un agent ne peut évidemment se choisir lui-même
Je souhaiterais qu'excel puisse "matcher" automatiquement les agents souhaitant être ensemble.
Dans l'onglet "souhaits", seraient cochés les souhaits de chacun des agents
Idéalement, l'onglet résultat afficherait les binômes déterminés
Un problème va cependant se poser (peut-être même plus mais mon expertise en la matière s'arrête là
si plusieurs agents, disons 1,2,3,et 4 veulent être avec le même autre agent, disons 5, je souhaiterais afin de ne pas compliquer encore plus les choses, que ce soit le 1er agent qui matche qui soit retenu, ce qui donnerait dans notre exemple un binôme 1-5.
A moins que d'autres solutions soient envisageables bien entendu, cela me semble plus simple, bien que moins "juste".
J'imagine qu'il faille passer par du VBA, d'autant plus que je ne disposerai que de quelques minutes, une fois les souhaits saisis, pour que les binômes soient déterminés.
Je vous remercie par avance,
Cordialement,
Bonjour,
J'imagine qu'il faille passer par du VBA
pas nécessairement, si vous faite une liste en colonne A et B
par exemple:
1 50
2 49
3 48
. .
. .
49 2
50 1
ou bien
1 25
2 24
. .
. .
24 2
25 1
. .
. .
49 27
50 26
ajouter en conlonne C
les souhaits, si il y en a que quelque un vous pourrai alors "junglé" un peu avec ceux-ci
ou bien
utiliser un randbetween vis-à-vis une liste de nom (vba)
Sub test1()
'sans doublon
Dim v1 As Integer, i As Integer
Set dico1 = CreateObject("Scripting.Dictionary")
Do Until i = [B1] - [A1] + 1
v1 = Int(([B1] - [A1] + 1) * Rnd() + [A1])
If Not dico1.Exists(v1) Then
dico1.Add v1, v1
i = i + 1
End If
Loop
[B2].Resize(i) = Application.Transpose(dico1.keys)
End SubSalut Pizouille,curulis57,
désolé j'ai fait un erreur sur les formules Test, voilà c'est corrigé sur ce fichier
Merci à vous pour vos retours.
Je regarde ça ce soir en rentrant.
curulis57 a écrit :Salut Pizouille,SabV,
une idée tordue à tester...
A+
Merci, le concept me plaît beaucoup, par contre je ne comprends pas pourquoi certains binônes qui se choisissent réciproquement n'apparaissent pas en binômes.
J'ai fait un test ou l'agent 1 choisit l'agent 2 et l'agent 2 choisit l'agent 1 mais l'association se fait avec d'autres binômes..
Merci par avance,
Salut Pizouille,
pour éviter que les premiers de liste soient toujours les mieux servis, j'effectue un random pour choisir à chaque boucle un participant au hasard pour lequel je prends le premier choix encore disponible.
C'est dans la Bible, hein,
J'effectue 250 essais, chacun enregistré dans un tableau. Une autre boucle choisit alors dans ces essais celui qui a 'matché' le plus de binômes, résultat d'ailleurs qui ne peut être nullement garanti même avec 1.000.000 d'essais : il peut toujours y avoir un mal-aimé dans le groupe qui n'est jamais choisi par les autres!
A+
Merci à toi Curulis57, j'adore ta solution et la mettre en application.
En parlant de bible, tu es en quelque sorte une divinité
Bonne continuation et merci encore
sabV a écrit :Salut Pizouille,curulis57,
désolé j'ai fait un erreur sur les formules Test, voilà c'est corrigé sur ce fichier
Merci SabV pour la solution proposée; dans les conditions professionnelles dans lesquelles je vais être confronté, ce que m'a proposé Curulis57 matche à 100% avec mon besoin.
Un grand merci à toi pour ta solution.
Cordialement,
Bonsoir à tous,
Salut Curulis !
Pas eu le temps de regarder ta solution, car je m'étais lancé sur la question pour essayer de me remettre en forme pour la journée...
J'avais oublié que je venais d'avaler un comprimé dont je sais que l'effet sur moi est assez hautement soporifique (je n'en prends jamais plus d'un par 24h, car la c'est la cata).
De toutes façons j'aurais pu faire n'importe quoi, le résultat aurait été le même !
Pizouille, j'ai repris ton idée d'affecter selon les premières demandes trouvées, mais en procédant toutefois à un tirage aléatoire.
On aboutit ainsi à ce qu'environ la moitié aient un voeu satisfait et l'autre moitié non... Cela peut varier selon la dispersion des voeux, mais ici je distribue les voeux préalablement de façon aléatoire, la proportion devrait donc être toujours assez stable à 50%-50%. Sur des voeux réels découlant d'affinités et donc avec une certaine réciprocité, la proportion de voeux satisfaits devrait sensiblement augmenter.
Pour tester, il y a un bouton qui lance une procédure en vue du test : efface les voeux (et les résultats) et remplit des voeux de façon aléatoire.
On peut alors lancer la proc. de création des binômes. Elle effacera de toutes façon les résultats.
J'ai aussi ajouté un bouton Effacer qui efface voeux et résultats. En réel son utilité est d''effacer les voeux, pour en mettre d'autres (non définis aléatoirement !)
J'ai une autre idée, pour essayer d'accroître le degré de satisfaction des voeux... J'écrirai ça à un moment où j'aurais un peu plus de vivacté, pour tester l'idée. La constitution de binômes ou trinômes ou plus à partir de voeux est un problème qui revient régulièrement.
Cordialement.
Salut Pizouille, SabV
Bien le bonjour MFerrand!
Nous jetterons un voile pudique sur ton appréciation... enthousiaste! 8)
D'autant que... je ne comprends plus mes propres lignes que j'ai cherché à améliorer...
Ça fonctionne sans que je ne sache plus trop comment... et la version d'hier, en la relisant, était catastrophique...Faut le faire...
Bref, je continue à chercher mes Gremlins!
Dans la plupart des cas, ça matche à 100%... même si, parfois, un Gremlin empêche l'affichage du 25e binôme.
Quand c'est incomplet (malgré 1000 essais), un autre Gremlin me mange la moitié du binôme manquant!
Dans ces cas-là, un reclic sur le bouton rouge relance le calcul. Finira bien par trouver!
A+
Bonjour Curulis, bonjour MFerrand,
J'aime beaucoup vos approches respectives et vous remercie pour le temps passé.
Pour le coup, je viens d'avoir des indications contradictoires par rapport à la commande initiale.
Au lieu d'avoir à matcher 50 personnes, celles-ci seraient regroupées par groupe de 10 et ne pourraient effectuer que 5 choix au sein de leur groupe respectif.
Donc, il suffirait d'avoir la même approche mais uniquement sur une population de 10 agents.
Serait-il possible dans ce cas de figure de prioriser les binômes qui se choisissent réciproquement, de les binômer en priorité; et pour ceux qui ne se sont pas réciproquement choisis, de respecter au moins 1 de leur souhaits ?
Merci par avance, et encore désolé pour l'info contradictoire qui m'a été donnée.
Cordialement,
J'omets un détail important :
puisque la population est restreinte à 10 agents, il y a de très fortes probabilités pour que plusieurs personnes se choisissent réciproquement, ce qui n'arrange pas la constitution de binômes
Je souhaiterais donc donner un "poids" à chacun de ses 5 souhaits, par ordre de préférence. (de 1 : souhait prioritaire à 5 : souhait minimal), et d'arranger les binôme en fonction de leur souhait prioritaire.
Cela vous paraît-il envisageable ?
Merci par avance
Bonsoir,
J'ai dû quelque peu prolonger mes séances de sommeil d'hier... mais entre deux séances je suis parvenu à finaliser la 2e version, basée principalement sur les choix !
Sub CréerBinomesChoix()
Dim Tb(), Tbs(), Ttmp, d As Object, k, i%, j%, h%, a%, b%, x%
Set d = CreateObject("Scripting.Dictionary")
With [Liste]
For i = 1 To .Rows.Count - 1
For j = i + 1 To .Rows.Count
k = i & Chr(215) & j
For h = 1 To 5
If .Cells(i, h + 1) = j Then a = h
If .Cells(j, h + 1) = i Then b = h
If a > 0 And b > 0 Then Exit For
Next h
If a = 0 Then a = 9: x = 9
If b = 0 Then b = 9: x = 9
If x = 0 Then x = IIf(a < b, a, b)
x = (a + b) * 10 + x
d(k) = x
a = 0: b = 0: x = 0
Next j
Next i
End With
ReDim Tbs(d.Count, 2): h = 0
For Each k In d.keys
h = h + 1: Tbs(h, 2) = CInt(d(k)): Tbs(h, 1) = k
Next k
For i = 1 To h - 1
For j = i + 1 To h
If Tbs(i, 2) > Tbs(j, 2) Then
Tbs(0, 2) = Tbs(j, 2): Tbs(j, 2) = Tbs(i, 2): Tbs(i, 2) = Tbs(0, 2)
Tbs(0, 1) = Tbs(j, 1): Tbs(j, 1) = Tbs(i, 1): Tbs(i, 1) = Tbs(0, 1)
End If
Next j
Next i
ReDim Tb(1 To [ListeB].Rows.Count, 0): j = 0: Tbs(0, 2) = 0
For i = 1 To h
If Tbs(i, 2) <> Tbs(i - 1, 2) Then j = j + 1
Tbs(i, 0) = j
Next i
For i = 1 To h
x = Tbs(i, 0): j = 0
Do While Tbs(i + j + 1, 0) = x
j = j + 1
If i + j = h Then Exit Do
Loop
For x = 0 To j
If Tbs(i + x, 1) <> "" Then Ttmp = Ttmp & ";" & Tbs(i + x, 1)
Next x
If Ttmp <> "" Then
Ttmp = Split(Ttmp, ";"): Ttmp(0) = UBound(Ttmp)
Else
Ttmp = Split(";", ";"): Ttmp(0) = 0
End If
Do While CInt(Ttmp(0)) > 0
x = Int(UBound(Ttmp) * Rnd + 1)
k = Split(Ttmp(x), Chr(215)): a = CInt(k(0)): b = CInt(k(1))
Tb(a, 0) = b: Tb(b, 0) = a
For x = 1 To UBound(Ttmp)
k = Split(Ttmp(x), Chr(215))
If CInt(k(0)) = a Or CInt(k(0)) = b Or CInt(k(1)) = a Or CInt(k(1)) = b Then
Ttmp(x) = "@": Ttmp(0) = CInt(Ttmp(0)) - 1
End If
Next x
Ttmp = Join(Ttmp, ";"): Ttmp = Replace(Ttmp, ";@", "")
If InStr(Ttmp, ";") = 0 Then Ttmp = Ttmp & ";"
Ttmp = Split(Ttmp, ";")
For x = i To h
If Tbs(x, 1) <> "" Then
k = Split(Tbs(x, 1), Chr(215))
If CInt(k(0)) = a Or CInt(k(0)) = b Or CInt(k(1)) = a Or CInt(k(1)) = b _
Then Tbs(x, 1) = ""
End If
Next x
Loop
Ttmp = "": i = i + j
Next i
[ListeBChoix].Offset(, 1).Value = Tb
End SubCette procédure opère en recensant tous les binômes possibles (1225 pour 50 participants) et en attribuant à chaque binôme théorique une valeur en fonction des choix réciproques des deux membres. Les binômes sont classés par valeur. On tire au sort s'il y a lieu dans chaque groupe de même valeur, et à chaque sélection d'un binôme on élimine de la liste tous les binômes théoriques auxquels les deux membres choisis participaient avant de passer au choix suivant...
Si ça fonctionne pour 50, ça fonctionnera aussi pour 10 !
Mais si tu as une étapre intermédiaire, dans le processus global, de constitution des groupes de 10, on peut prendre la chose au départ, pour constituer ces groupes, s'il ne sont pas préconstitués et ensuite créer les binômes pour chaque groupe. On ajoute les proc. nécessaires et toute l'opération peut se faire d'un seul tenant.
Cordialement.
Salut Pizouille,
voilà ton fichier à 10 agents avec des choix prioritaires.
Tu dois bien te dire que, si plusieurs agents choisissent la même gueule d'ange comme choix 1, il y aura des malheureux!
Tu peux, de toute façon, cliquer autant de fois sur le bouton rouge pour matcher un max de 1er choix :
- vert : 1er choix ;
- bleu : 2e choix ;
- orange : 3e et 4e choix ;
- rouge : 5e choix.
Ici, pour le test, à chaque clic sur le bouton, la macro redistribue aléatoirement les choix de chaque agent.
Le code à éliminer est repéré en début de macro.
A+
En prime, la version 50 agents corrigée mais sans priorités de choix comme tu l'avais demandé à l'origine.
Un grand merci à vous Curulis57 et MFerrand,,
La session s'est extrêmement bien déroulée.
Bien cordialement,
MFerrand a écrit :Cette procédure opère en recensant tous les binômes possibles (1225 pour 50 participants) et en attribuant à chaque binôme théorique une valeur en fonction des choix réciproques des deux membres. Les binômes sont classés par valeur.
Il y a 49*47*55*43 ... soit 10^31 possibilités avec 50 personnes.
Si tu n'en a que 1225, ou même que le calcul termine, c'est qu'il y a une erreur
Par contre, pour 10, il y a 945 possibilités, l'analyse exhaustive est faisable, et se fait sans macro.
démonstration :
on donne un n° de 1 à 50 à chaque personne
quel que soit le binome, on mets le plus petit devant
on ordonne les binomes en triant par le premier du binome
Avec cette écriture, chaque arrangement équivalent s'écrit exactement de la même manière, et l'écriture est unique (paf, bijection)
Et le dénombrement de cette écriture est :
le premier est toujours 1
pour le deuxième, il y a 49 choix.
Le troisième est toujours 2, sauf s'il a été choisi par le premier auquel cas c'est 3, bref, c'est fixe
pour le quatrieme, il y a 47 choix possibles
Etc. 49*47*45 ...
Je ne vous le coderais pas, mais voici un algorithme efficace pour faire la recherche opérationnelle sur les 50 participants :
a) en parcourant la liste au hasard, on identifie une personne qui a une seule attirance reciproque, et on forme ce binome
b) on répète a) jusqu'à ce qu'il n'y n'en trouve plus
c) en parcourant la liste au hasard, on identifie une personne qui a deux attirances reciproques, et on forme l'un de ces binome au hazard, puis on passe à d) (on répète pas c)
d) si il n'y a pas de cas avec deux attirances réciproque, chercher avec 3 ou plus. (puis on passe à e)
e) on revient en a)
f) a ce stade, il n'y a plus une seule attirance réciproque, on reproduit alors les étapes a à e sur les attirances simples
g) à ce stade, il n'y a plus d'attirances du tout, on forme les derniers binômes au hazard.
Edit :
on peut encore améliorer cet algorithme, sans modifier l'ordre de chaque étape en rajoutant une étape de selection pour les étapes a) ou c) pour remplacer le hasard :
on fait la liste de toutes les personnes éligibles, et on liste tous les binomes possibles, et on calcule pour chaque binome le total des attirances que chaque membre a - dans un sens ou dans l'autre (émetteur ou récepteur) - en excluant les attirances avec des personnes qui ont déjà été sorties, et on choisi le binome qui a le plus petit nombre d'attirances. (en cas d'égalité, on prend le hasard)
Après, si on a encore 44 personnes éligibles et pas une seule qui a moins de 3 attirances, on abandonne cette optimisation jusqu'à ce que les nombres diminuent, car ce n'est pas calculable.
Peuwi ?
Je ne suis pas sûr d'avoir pu suivre tes raisonnements mais il s'agit de binômes, soit de groupes de 2, et lorsqu'on dénombre combien on peut en former de différents parmi un nombre donné de participants, il s'agit du nombre de combinaisons de 2 membres parmi 50...
Le nombre de combinaisons de p éléments parmi n est donné par la formule : FACT(n)/(FACT(p)*FACT(n-p)) [pour l'écrire façon Excel].
Mais il est facile de les dénombrer directement : le premier peut participer à 49 binômes, le second peut participer à 48 nouveaux binômes (hors ceux auxquels perticipe le premier...), le 3e à 47 nouveaux binômes, ainsi de suite jusqu'au 49e qui peut encore participer à 1 nouveau binôme avec le 50e (lequel n'a plus de possibilité supplémentaire). Le nombre total de binômes possible correspond donc à la somme des nombres de 49 à 1, ce que l'on peut faire par
Le nombre de combinaisons est 1225 pour 50, je confirme, et 45 pour 10 !
Ce qui permet effectivement les recenser...
Cordialement.