Excercice de Combinatoire

Question

Voici l'enonce de mon probleme et l'avance de mes recherches.



1/ Question: 
Je fais un tirage de 4 elements (= quadruplets) parmi une liste de 12 elements. La methode de tirage est ordonnee, c'est a dire ABCD <> CDAB. Sous Excel, via la macro nommee "ListPermutations" deja publiee, on obtient facilement l'ensemble de toutes les combinaisons de quadruplets, soit 11880 au total.
Maintenant mon probleme: je souhaite selectionner 99 quadruplets de sorte que l'ensemble de toutes les paires dans les quadruplets se repetent au total 9 fois (Dans le quadruplet ABCD il y a 3 paires AB / BC et CD).



2/ Mon code:
J'ai decide d'aborder mon probleme par selection-elimination de paires et quadruplets, n'etant pas un "matheux", c'etait la seule solution que j'avais.
Je n'obtiens malheuresement pas ma / mes solution(s), mis-a-part des demi-solutions telles que listes de 99 quadruplets avec repetition de 4 paires...

3/ Dans la suite de mes recherches, je suis tombe sur des mots-cles tels que "Balanced Incomplete Block Design"... et autres langages mathematiques permettant de resoudre entre autres les problemes de combinatoires "GAP", "MAGMA"...

--> Je pose ma question aux membres de ce forum car je suis a bout d'idees. Quelqu'un aurait-il connaissance d'algorithmes ou d'approches permettant de resoudre ne serait-ce meme une petite partie de mon probleme?

Cordialement,
Dido.

marinmarais · Answer

Salut didorun,
Alors j'ai bien compris le debut. Tu definis les differents arrangements de 4 elements parmi 12. Le nombre d'arrangements est donne par : A(12,4) (12!) / ((12-4)!) 11880

Par contre je n'ai pas compris la selection que tu veux faire parmi ces arrangements, notammant ces histoires de paires qui se repetent...

A+
Tom.

Marin Marais

didorun · Answer

Je souhaite effectuer une selection selon les criteres suivants:

1/ definir 99 arrangements de 4 elements parmi 12 (= 11880 choix possibles)

2/ sur le total de 99 arrangements, avoir le maximum de paires a savoir que sur 12 elements il y a (12,2) = (12!) / ((12-2)!) soit 132 paires possibles.
Pour un arrangement A.B.C.D., les differentes paires seront: A.B - B.C - C.D - et D.A.

De facon a illustrer tout cela, confere le schema ci-dessous.

Une fois ma selection de 99 arrangements faite, je souhaite avoir un total de 9 paires idealement, moins si ce n'est pas possible. Dans l'exemple, selon ma selection d'arrangement, la paire A.C. apparait 2 fois.

J'espere que c'est un petit peu plus clair.
Cordialement,

Didorun.

didorun · Answer

Ooops, avec le schema attache, c'est mieux: ---- , PERMUTATIONS, ---- , 1, 2, 3, 4, ---- 1, A, B, C, G, ---- 2, A, C, F, L, ---- 3, A, C, I, E, ---- 4, A, D, F, B, ---- 5, A, E, J, H, ---- 6, A, F, D, E ... jusqu'a 99 ---- PAIRES PAR ARRANGEMENTS, ---- PAIRS1, PAIRS2, PAIRS3, PAIRS4, ---- AB, BC, CG, GA, ---- AC, CF, FL, LA, ---- AC, CI, IE, EA, ---- AD, DF, FB, BA, ---- AE, EJ, JH, HA, ---- AF, FD, DE, EA Soit pour le compte des paires: ---- TOTAL DE PAIRES /, ---- 99 PERMUTATIONS, ---- AB, 1, ---- BC, 1, ---- CG, 1, ---- GA, 1, ---- AC, 2, ---- CF, 1 ... jusqu'a 132.

Excercice de Combinatoire

3 réponses

Votre réponse

Discussions similaires