Pour les besoins d'une activité interactive Flash, j'ai cherché un algorithme permettant d'obtenir toutes les combinaisons ordonnées avec remise de k éléments d'un ensemble de n éléments.
Je n'ai codé que la fonction arrangements_ordre_remise pour l'instant, les autres cas renvoient le nombre de combinaisons sans les énumérer.
Pour une petite révision : wikipedia/combinatoire
function combinaisons (tabElems, NbElemComb, ordre, remise) { // si pas ordonnée ou pas de remise, NbElemComb doit etre inférieur au nombre d'elements : if (((ordre == false) or (remise == false)) and (NbElemComb >= tabElems.length)) { return -1; } // calcul du nombre de combinaisons : cnp = 0; n = tabElems.length; if (ordre) { if (remise) { // n puissance p cnp = Math.pow (n, NbElemComb); resultat = new Array(cnp); resultat = arrangements_ordre_remise (tabElems, NbElemComb, cnp); } else { trace ("Arrangements ordonnés sans remise : "); // n! / (n-p)! cnp = Math.factorielle(n) / Math.factorielle (n-NbElemComb); resultat = new Array(cnp); return cnp; //resultat = arrangements_ordre_noremise (resultat, tabElems, NbElemComb); } } else { if (remise) { trace ("Combinaisons avec remise : "); // ((n+p-1)! / (n-1)!) / p! n1 = n + NbElemComb - 1; cnp = (Math.factorielle(n1) / Math.factorielle (n1-NbElemComb)) / Math.factorielle (NbElemComb); resultat = new Array(cnp); return cnp; //resultat = combinaisons_remise (resultat, tabElems, NbElemComb); } else { trace ("Combinaisons sans remise : "); // (n! / (n-p)!) / p! cnp = (Math.factorielle(n) / Math.factorielle (n-NbElemComb)) / Math.factorielle (NbElemComb); resultat = new Array(cnp); return cnp; //resultat = combinaisons_noremise (resultat, tabElems, NbElemComb); } } return resultat; } function arrangements_ordre_remise (tabElems, NbElemComb, cnp) { res = new Array(cnp); for (i=0; i<cnp; i++) { res[i] = new Array(NbElemComb); } // de 0 au nombre d'element dans une combinaison : for (increment = 0; increment < NbElemComb; increment++) { // remettre a zéro les compteurs : indexComb = 0; indexVal = 0; factor = Math.pow (tabElems.length, (increment+1)); // ex : // tabElems = [0,1,2,3] // NbElemComb = 3 // --> cnp = 4 puissance 3 = 64 // increment = 0 // --> factor = 4 // --> cnp/factor = 16 // --> 16 x 0 - 16 x 1 - 16 x 2 - 16 x 3 // ... for (i=0; i<factor; i++) { for (j=0; j<(cnp/factor); j++) { res[indexComb][increment] = tabElems[indexVal]; indexComb++; } indexVal++; if (indexVal == tabElems.length) { indexVal = 0; } } } return res; } Math.factorielle = function(x) { if(Math.abs(Math.floor(x))==x) { return ((!x)? 1 : x*Math.factorielle(x-1)); } else { return false; } }
Commentaires
Aucun commentaire pour le moment.
Ajouter un commentaire