Combinaison.js

10 décembre 2012 à 11:05:43

Bonjour, j'essaye d'ecrire une fonction qui retourne le nombre de combibnaisons sans répétition de n éléments pris p à p. Voici mon code.
var comb=function(n,p){

var comb=function(n,p){

    var Cnp;

    if(n<p || n<0 || p<0){

        Cnp=0;

    }

    else if(p==0 || n==p){

        Cnp=1;

    }

    else Cnp=comb(n-1,p-1)+comb(n-1,p);

    return Cnp;

};

Voila. Je me demandai comment je pouvais afficher le résultat de ces combinaisons? j'ai essayé avec :

print(comb([1,2,3],3));

Mais rien ne s'affiche lorsque j’exécute le code, même si j’enlève le print. ça peut paraitre un peu bête comme question mais j'ai plusieurs fonctions récursive qui me posent le même problème. la fonction continue de s'appeler elle même sans arrêt jusqu’à ce que mon navigateur freeze. Inutile de me proposer une version itérative je voudrai comprendre le fonctionnement de ce genre de fonctions récursives.
Au cas ou je n'ai pas été clair ma question est "comment afficher toutes les combinaisons(sous forme de tableau par exemple)?"

Rouls

10 décembre 2012 à 11:16:32

Citation : kingmehdi

var comb=function(n,p){

    var Cnp;

    if(n<p || n<0 || p<0){

        Cnp=0;

    }
...

tu compares une valeur a un tableau
n=array

il faut que tu parcours ton tableau pour pouvoir comarer les differentes valeurs a p

http://www.siteduzero.com/tutoriel-3-3 [...] -tableau.html

Anonyme

10 décembre 2012 à 14:35:26

La fonction parait bien écrite, mais il convient de l'appeler plusieurs fois dans une boucle si l'on veut traiter plusieurs cas.
Un exemple simple avec un script à la fin du body (pour que l'élément rsp existe lorsqu'il est appelé par son identifiant)

<body>
   <div id="rsp"></div>
<script type"text/javascript">
var comb=function(n,p){
    var Cnp;
    if(n<p || n<0 || p<0)Cnp=0;
    else if(p==0 || n==p)Cnp=1;
    else Cnp=comb(n-1,p-1)+comb(n-1,p);
    return Cnp;
};
for (var i=0;i<33;i++) document.getElementById('rsp').innerHTML+='<p>Nombre de tirages de '+i+' cartes parmi 32 : '+comb(32,i)+'</p>'; 
</script>
</body>

L'utilisation d'une fonction récurrente est sympathique mais risque d'être un peu lourde en javascript. La variante suivante est sans doute moins sujette à saturation de la pile (stack overflow).

var comb=function(n,p){
    var Cnp;
    if(n<p || n<0 || p<0) Cnp=0;
    else Cnp=1;
    while (0<p) Cnp*=n--/p--;
    return Math.round(Cnp);
};

kingmehdi

11 décembre 2012 à 6:18:19

Tout d'abord je te remercie pour avoir pris le temps de me répondre, j'ai bien spécifié que ma question étais exclusivement relié au cas récursive, je sais très bien que dans certains cas la méthode itérative est plus convenable. Ceci étant dit, comme je suis débutant en Javascript, que je ne m'y connais pas en HTML, j’exécute mon code simplement sur un environnement interprète de JS, du coup j'essaye d'afficher le résultat de la combinaison simplement avec des commandes JS.
Si j'ai bien compris je dois utiliser n.length au lieu de n, c'est bien ça? Lorsque je le fais. je termine mon code avec un :

print([1,2,3],3]);

et celà me donne 1 comme resultat? comment faire pour pouvoir afficher le resultat de ma fonction recursive sous la forme 1,2,3 1,3,2.....

Anonyme

11 décembre 2012 à 13:28:34

La fonction est construite pour travailler avec des entiers n et p et calculer le nombre de combinaisons de n objets pris p à p. Il n'est donc pas question de l'appeler avec un vecteur (or an array du type [1,2,3]) !

Ensuite pour afficher un résultat avec une commande js. La commande alert(comb(7,3)) permet d'économiser le papier tout comme console.log() qui a la faveur des développeurs (voir, par exemple, cette page).

Maintenant pour obtenir les permutations de plusieurs éléments, on peut utiliser la décomposition unique de tout entier inférieur à n! sur 0!, 1!,... (n-1)! pour numéroter les permutations (de 0 à n!-1).

La construction de la permutation 13 de 4 éléments '1234' s'effectue alors comme suit.
Partant de 13 = 2*3! + 0*2! + 1*1! + 0*0!, on prend successivement les éléments de rang 2,0,1 et 0 (rangs comptés à partir de zéro) de la chaîne '1234'. Ce qui donne 3 avec la chaîne résiduelle '124', puis 1 reste '24' puis 4 et 2. D'où la permutation '3142'.

La mise en œuvre de cette construction des permutations peut alors s'opérer comme suit (avec une numérotation plus usuelle de 1 à n!, ce qui classe la permutation précédente au rang 14).

<script type="text/javascript">
function prm(n){var i,j,k,sto='',tbo=[];
// Construire la chaine sto '123...n' et le tableau tbo [0!,1!,2!,3! ...(n-1)!]
	i=0;while (i<n) {tbo[i]=0<i?tbo[i-1]*i:1;sto+=++i;}
// Boucler sur les permutations numérotées de 0 à n!-1
	var nos,str,prm,rtr='';
	for (i=0;i<tbo[n-1]*n;i++){
		nos=i;k=n;str=sto;prm='';
		while(k--) {j=Math.floor(nos/tbo[k]);nos%=tbo[k];
			prm+=str.substr(j,1);str=str.substr(0,j)+str.substr(j+1);}
	   rtr+='n°'+(i+1)+' '+prm+'\n';
	}
	return rtr;
}
alert(prm(4))
</script

EDIT : Reste à se limiter aux combinaisons de p entiers pris parmi n !

kingmehdi

11 décembre 2012 à 16:48:12

Ta fonction est-elle récurrente? car dans le cas contraire n'importe quelle version itérative du programme ne me sert à rien, j'ai bien spécifié que je voulais travailler sur la version récurrente... Je veux bien qu'on me donne des pistes, mais on continue à sortir des versions itérative alors que j'insiste que c'est inutile et que je veux que les réponses ne concernent que la version récurrente? Pour ceux qui connaissent la réponse mais en itératif, merci d'avoir fait un saut sur le sujet, ce dernier n'est pas pour vous. J'ai posé une question ciblé, je préfère avoir une réponse ciblé et non pas chacun proposant des solutions qui n'ont absolument rien à voir avec ma question. Je specifie qu'il s'agit d'une question sur LA RECURENCE! et non pas sur quoi que ce soit comme version itérative. Merci d'avance!

lavoghis

11 décembre 2012 à 20:54:20

Salut,

Je veux bien t'aider mais je veux être certain de ce que tu cherche à sortir. Tu as deux paramètres le premier semble être les différent nombre que tu veux utiliser dans les combinaisons. Les deuxième nombre semble être le nombre de chiffre dans la combinaison. Est-ce que c'est ça? Car dans ton exemple il n'y a une seul combinaison soit «123». D'après moi tu parles de permutation soit «123» «132» et comme dans le dernier exemple de 007Julien. Soit plus claire et je t'aiderai dans ta fonction récursive.

@+, Ghislain

Anonyme

11 décembre 2012 à 21:07:46

Effectivement, il s'agit, semble-t-il malgré l'intitulé, d'afficher, en utilisant une fonction récurrente, tous les arrengements de n objets pris p à p !

Toutes mes excuses, je n'avais décidément rien compris à ce sujet.

kingmehdi

11 décembre 2012 à 21:57:04

Voici l'utilité exacte de la fonction .Il doit s'agir d'une fonction récursive comb(n,p) qui retourne le nombre de combinaisons sans répétition de n éléments pris p à p. Ce nombre de combinaisons (aussi noté Cnp) est défini par la récurrence:

comb(n,p) = 0 si n < p ou n < 0 ou p < 0
1 si p = 0 ou n = p
comb(n-1,p-1) + comb(n-1,p) sinon

Anonyme

12 décembre 2012 à 0:58:19

Dans ce cas toutes nos félicitations, la fonction initialement proposée est parfaite, encore conviendrait-il de ne pas attendre d'elle l'affichage de tableaux d'arrangements !

kingmehdi

12 décembre 2012 à 6:49:31

comment ça? il ne m'est pas possible à l'aide d'un alert ou print d'obtenir les arrangements?
Voici par exemple une fonction récurrente qui prend en paramètre un tableau de pièces, et un montant globale. Le but de cette fonction est de me donner le moins d'utilisations possibles de chaque pièce. Supposons que j'ai les pièces [1,2,5,10] et le montant globale est 17. Dans ce cas là la fonction doit me retourner le tableau suivant [0,1,1,1]c'est à dire que la solution optimale est l'utilisation d'une pièce de 10, une de 5 et une de 2. J'ai le méme souci que la fonction d'avant je n'arrive pas à afficher le tableau que je suis censé avoir.Voici ma fonction :

var change=function(pieces,montant){

    
     var t= Array();

    
     if(montant == 0) 
        return 1;
   
     if(montant <0) 
        return 0;
     if(pieces.length<=0)
         return 0;
    
     else{ 
         var a= change(pieces.length - 1, montant);
         var b= change(pieces.length, montant - t[pieces.length]);
         
         return a+b; 
         
      
                      }; 
 
};

La fonction est-elle correcte, et si oui, comment afficher le tableau voulu dans l'exemple precédent.

Anonyme

12 décembre 2012 à 13:18:17

Une fonction récurrente pour payer un montant (m) avec le minimum de pièces de valeurs (v).

function payer(m,v,n,r){var i;
// initialisation 
   if(!n) {n=new Array(v.length+1).join('0').split('');
	var r='Pour payer '+m+' euro'+(1<m?'s':'')+' avec le minimum de pièces utilisez :\n';}
// Mise en forme finale
	if (m==0){i=v.length;while(i--) if (n[i]!=0) r+=' '+n[i]+' pièce'+(1<n[i]?'s':'')+ ' de '+v[i]+ ' euro'+(1<v[i]?'s':'')+','; 
		alert(r.substr(0,r.length-1).replace(/,([^,]+)$/,' et$1')+'.');return}
// Corps de la fonction
	i=v.length;while (i-- && m<v[i]);
	n[i]++;payer(m-v[i],v,n,r);
}
for (i=13;i<28;i++) payer(i,[1,2,5,10]);

Le principe consiste à utiliser, à chaque itération, la pièce de plus grande valeur possible...
A moins d'utiliser des variables globales, il est indispensable de passer les valeurs en argument et de les construire lorsqu'elles n'existent pas (tableau n des nombres de pièces de chaque valeur construit lors de la première itération) ou de les stocker pour pouvoir les afficher en fin de l'itération (montant m stocké dans r pour construire la réponse).

Il ne reste plus qu'à réaliser, car telle était la question, une fonction récurrente du même genre pour afficher tous les arrangements de n objets pris p à p.

Bon courage...

MathieuLandreau2

1 mai 2018 à 20:00:21

D'un point de vue purement Math et pas du tout Prog:

comb(n,p) = n!/(p!*(n-p)!)

Dommage que j'arrive 6 ans trop tard hehe

Combinaison.js

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.

× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.

Combinaison.js

Combinaison.js

Supprimer

Modérer

Signaler le message aux modérateurs