XL 2016 liste des combinaisons possibles d'appairage 2 à 2 parmi N

[pyfalquet]

Bonjour,

Je travaille sur une problématique de rééquilibrage de stocks sur un réseau de boutiques de N points de ventes (N étant un nombre paire qui peut varier dans le temps). Pour se faire, je dois "appairer" 2 à 2 mes points de ventes et tester toutes les combinaisons possibles . Par exemple, si le réseau est composé de 6 boutiques A, B, C, D, E, F, il faut que je puisse établir toutes les associations possibles :
-combinaison 1 :A associé à B /C associé à D/E associé à F
-combinaison 2 : A associé à B/ C associé à E/D associé à F
-combinaison 3 : A associé à C/ B associé à D/ E associé à F
....etc
J'ai établi de manière exhaustive toutes ces combinaisons pour un parc de 36 boutiques (soit 595 combinaisons) qui s'affichent dans un tableau excel . Ces combinaisons me servent ensuite pour mes calculs d'optimisation de rééquilibrage (en pratique, je fais une analyse de scénario sur excel avec ces 595 combinaisons, qui donne une valeur finale pour chacune d'entre elles)
Ma question est la suivante:
j'aimerais pouvoir générer automatiquement toutes les combinaisons possibles d'appairage 2 à 2 pour N variable (N étant un nombre paire compris entre 8 et 50) présenté si possible comme dans le fichier en PJ (les boutiques sont représentées par des numéros de 1 à N, appairées 2 à 2 .)
Je vous remercie de l'aide que vous pourrez m'apporter sur ce sujet
Bien à vous
Pfalquet

 

[Graveling]

Salut,

Je ne suis pas sur que ton fichier excel soit si exhaustif...dans le cas de 36 boutiques, rien que pour le premier appairage, je trouve beaucoup plus de combinaison que les 595 au total.

Pour un choix de 2 parmi 36, on a la formule suivantes: 36!/(2!*(36-2)!) soit un total de 630 combinaisons!

En gros, on a pour le premier doublon 36 choix pour la première valeurs et 35 choix pour la deuxième soit 36*35, et on divise par 2 pour enlever les doublons (A et B est identique à B et A). Et ainsi de suite pour les suivants (34 * 33)/2 pour le deuxième appairage, et ainsi de suite... tu te retrouves avec un nombre de combinaison énorme...je ne suis pas sur qu'excel ait assez de lignes pour chacune des combinaisons.

 

[Dranreb]

Bonsoir
Ces deux fonctions perso pourraient peut être vous intéresser :

Public Function VersusJA(ByVal J As Long, ByVal A As Long) As Long
   If A < J Then A = A Xor J: J = J Xor A: A = A Xor J
   If A > J Then VersusJA = A * (A - 3) \ 2 + J Else VersusJA = -1
   If VersusJA < 0 Then Err.Raise 9999, , "VersusJA(" & J & ", " & A & ") impossible."
   End Function
Public Function JAVersus(ByVal VS As Long)
   Dim J As Long, A As Long
   A = Int(Sqr(2 * VS + 0.25) + 1.5)
   J = VS - A * (A - 3) \ 2
   JAVersus = Array(J, A)
   End Function

Mais il semble que 595 appariements possibles (numérotés de 0 à 594) ce serait plutôt pour 35 boutiques (numérotées, elles, de 1 à 35). Pour 36 boutiques ce serait plutôt 630 appariements possibles.

Remarque: ce calcul est utilisé dans ce Tirage aléatoire tous versus à nombre de terrains limité.

 

[Graveling]

Oui cest 630 pour juste le premier appairage, ensuite 561 pour le 2nd, 496 pour le 3eme et ainsi de suite pour avoir tous les appairages possibles. Ils se multiplient tous entre eux...il y a déjà plus de 350 000 combinaison pour appairer 4 boutique entre elle 2 à 2 parmi 36...et 175 000 000 de combinaisons pour 6 boutiques appairer entre elle 2 à 2 parmi 36...

 

[Dranreb]

Je dois avouer que je n'avais pas ouvert le classeur de pyfalquet, et n'avais pas bien compris le but.
Cette fonction, utilisable entre autres dans une formule matricielle horizontale, renvoie une table de Long à partir d'un numéro de combinaison et un nombre de paires à traiter. Mais je crois que c'est très vite limité à pas plus d'une demi douzaine de paires de boutiques environ, à mon avis, si on veut toutes les lister.

Function Appariement(ByVal Numéro As Long, ByVal NbPaires As Long)
   Dim T&(), N&, M&, P&, W&
   ReDim T(1 To 2 * NbPaires)
   For N = 1 To UBound(T): T(N) = N: Next N
   For N = 2 To UBound(T) - 2 Step 2
      M = UBound(T) - N + 1
      P = N + Numéro Mod M
      If P > N Then W = T(N): T(N) = T(P): T(P) = W
      Numéro = Numéro \ M
      Next N
   Appariement = T
   End Function

Le premier restitué c'est toujours le 1 (il faut bien qu'il soit toujours apparié à un autre. Le reste dépend de proche en proche du Numéro)
Le numéro spécifié commence à 0 et est considéré modulo le nombre maxi possible + 1, c'est à dire que s'il y a par exemple 2 paires et qu'on demande le numéro 3, il ressert le n° 0, parce qu'il n'y en a que 3 numérotées de 0 à 2.
À vérifier quand même compte tenu de l'ordre des combinaisons produites, dont la logique n'est pas évidente, et qu'il serait compliqué d'améliorer …

Le nombre de combinaisons de paires possibles en fonction du nombre de boutiques est donné par ce tableau :

Chaque fois qu'on ajoute 2 au nombre de boutiques ça multiplie le nombre de combinaisons jusque là possibles par ce nouveau nombre diminué de 1.
C'est normal: la première boutique peut être appariée à N - 1 autres, et pour chacun de ces cas il y a toutes les possibilités des N - 2 restantes.

 

[pyfalquet]

bonjour à tous,
Merci pour ces informations précieuses. J'avais effectivement vu que le nombre de combinaisons était bien de 630 et non de 595, mais je n'étais pas arrivé à retrouver les manquants. En revanche, je n'avais pas vu que ce nombre correspondait au seul premier appairage. Si je comprends bien le calcul de Dranreb, pour 36 magasins, il n'y a pas 630 mais 22164309547670000000 possibilités d'appairer les boutiques en 18 paires de 2?

 

[Dranreb]

Oui c'est cela.
Ça ne veut pas dire qu'on ne peut pas faire de recherche d'optimisation en en essayant un certain nombre durant un quart d'heure par exemple. On devrait pouvoir faire mieux en intervertissant au hasard deux magasins d'une combinaison prise d'un jeu d'une 40aine ou bien moins mais plus d'une à mon avis, et en y gardant cette nouvelle combinaison au détriment de la moins bonne du jeu si elle est meilleure qu'elle

 

[Dranreb]

Mais il vaudrait mieux fixer les combinaisons initiales par une procédure plus simple :

Sub InitListeAl(TAl() As Long, Optional ByVal NMax As Long, Optional ByVal Graine As Double)
   Dim P As Long, R As Long, X As Long
   If NMax >= 0 Then
      ReDim TAl(1 To NMax): For P = 1 To NMax: TAl(P) = P: Next P
   Else: NMax = UBound(TAl): End If
   If Graine <= 0 Then Randomize Else Rnd -1: Randomize Graine
   For P = NMax To 2 Step -1
      R = Int(Rnd * P) + 1: X = TAl(R): TAl(R) = TAl(P): TAl(P) = X
      Next P
   End Sub

 

[Dranreb]

Il y a probablement aussi quelque chose à faire à partir de l'apport individuel de chaque paire possible.
Ne serait-ce qu'en ne le calculant qu'une fois. Ma fonction VersusJA reprend du poil de la bête…

 

[pyfalquet]

Bonjour Dranreb
Merci pour toutes ces précisions. Malheureusement, je ne connais pas trop le VB et ne sais donc pas comment utiliser le programme que vous m'avez envoyé. Néanmoins, vos différents messages m'ont permis d'appréhender peut-être une solution à mon problème.
Je vais essayé d'être clair dans ma pensée à partir d'un exemple pour N=6:
Pour 6 magasins (numérotés de 1 à 6), nous avons bien 15 possibilités de les appairer 2 à 2 ( soit 3 binômes de 2). J'associe à chacune de ces 15 combinaisons une valeur numérique, résultat d'un calcul. Mon optimum se trouve pour la valeur la plus grande.
Par exemple, à la combinaison 1 avec 2 , 3 avec 4 et 5 avec 6, le calcul donne 1256.
En faisant le travail de manière exhaustif, on peut voir que la meilleure combinaison est 1-5/ 2-3/ 4-6 qui donne un résultat de 1856.
Pour N>14, on voit vite qu'un travail exhaustif est impossible au regard du nombre de combinaisons possibles.
En vous relisant, j'ai cru décelé un axe de travail qui pourrait s'assimiler, en probabilité, à la théorie de l'arrêt optimum, que l'on vulgarise souvent au travers du "problème du secréteriat": dans ce problème, on doit recruter une secrétaire parmi un très grand nombre de candidats (N). Soit on le fait de manière exhaustive en recevant tous les candidats, soit on sélectionne un groupe témoin de n candidats pris au hasard parmi les N, et dont on va déterminer le meilleur, qui servira de "référent". On reçoit ensuite un candidat n'appartenant pas au groupe échantillon: si celui-ci est meilleur que le référent du groupe n, on s'arrête là (optimum local), sinon, on reçoit un autre candidat et ainsi de suite...
Transposé à mon problème, l'idée serait de sélectionner n combinaisons au hasard parmi toutes les combinaison possibles et de regarder celle qui donne le meilleur résultat (le référent). Puis tester une à une, au hasard les autres combinaisons n'appartenant pas à l'échantillon jusqu'à ce que je tombe sur un résultat meilleur.
Qu'en pensez-vous?

combinaison	A1	A2	B1	B2	C1	C2		Résultat associé à cette combinaison
1​	1	2	3	4	5	6		1256​
2​	1	2	3	5	4	6		1345​
3​	1	2	3	6	4	5		1458​
4​	1	3	2	4	5	6		1222​
5​	1	3	2	5	4	6		856​
6​	1	3	2	6	4	5		987​
7​	1	4	2	3	5	6		1678​
8​	1	4	2	5	3	6		1547​
9​	1	4	2	6	3	5		1267​
10​	1	5	2	3	4	6		1856​
11​	1	5	2	4	3	6		1453​
12​	1	5	2	6	3	4		1356​
13​	1	6	2	3	4	5		1750​
14​	1	6	2	4	3	5		1333​
15​	1	6	2	5	3	4		1565​

 

[Dranreb]

Bonjour.
Oui c'est à peu près ma première idée du poste #7, mais j'en ai eu aussitôt une autre qui me semblait meilleure, basée plutôt sur l'idée de mutations aléatoires sur des combinaisons déjà pas mauvaises puis sélection naturelle (on sait que ça a donné un certain résultat dans le monde vivant, dixit Darwin …)

 

[Graveling]

Je t'avoue que le problème est intéressant, et l'approche me semble pas mal. Vu le nombre de combinaison pour 36 boutiques, tu n'as pas trop le choix pour réduire le nombre de solution.

 

[Dranreb]

Maintenant on pourrait peut être améliorer le principe de la mutation en la rendant moins aléatoire, en allant chercher dans un tableau triangulaire les paires les plus intéressantes. Je parlais de ma fonction VersusJA parce qu'elle sait calculer un indice vers un tableau à une dimension basé 0 d'après 2 indices différents spécifiés dans n'importe quel ordre, ce qui permet d'y accéder comme à un tableau triangulaire, où n'y sont notés les valeurs de couples que d'un coté de la diagonale, celle ci y étant exclue. La fonction JAVersus permet de faire l'inverse: elle retrouve le joueur et l'adversaire, heu… je veux dire les deux N°de magasins, correspondant à un indice dans la table à une dimension, indice que j'appelle le numéro de versus.