Algorithmique Combinatoire (AS1)

Soumis par Ricovitch le mar, 04/04/2006 - 22:00

Catégorie 

Flash, AS1, Math

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< 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<(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

Soumis par Anonyme le jeu, 11/26/2009 - 13:24

Bonjour Eric je viens de tomber sur ta méthode pour traiter les combinatoires. Je sais que ça date, mais si jamais par le plus grand des hasard, tu avais quelque part dans tes archives, la suite de la méthode, à savoir le "combinaisons_noremise", ce serait un grand moment de bonheur.

Merci d'avance :)

Ajouter un commentaire