/* combalea.js

	le nombre de combinaisons de p éléments de [1, n] est 
	binom(n, p) = binom(n-1, p) + binom(n-1, p-1)
	En effet une combinaison de p éléments de [1, n] est 
	  soit une combinaison de p éléments de [1, n-1]
	  soit la réunion de {n} et d'une combinaison de p-1 éléments de [1, n-1
	L'algorithme récursif suivant est alors enfantin :
	CombAlea(n, p) {
	    si (p<=0 ou p>n) {
		retourner [] // l'ensemble vide
	    } sinon {
	        On choisit au hasard un nombre x tel que 0 <= x < binom(n, p)
	        si (x < binom(n-1, p-1)) {
		     retourner CombAlea(n-1, p-1) + {n}
		} sinon {
		     retourner CombAlea(n-1, p) + {n}
		}
	   }
	}
*/

function binom(n,p) {
        if(p>n || p<0) return 0;
        if(p==0|| p==n) return 1;
        if(n-p<p) return binom(n, n-p);
        var u=1;
        for(var i=1; i<=p; i++) {
                u *=(n+1-i);
                u /= i;
        }
        return u;
}

function alea(n, p) {
return (n * Math.random() <  p) ? true : false;
}

function CombAlea(n, p) {
	if (p<=0 || p>n || n<0 ) {
                return "" // l'ensemble vide
        } else {
		
		if(alea(n, p)) {
			var s = CombAlea(n-1, p-1);
			if(s != "") {
				s +=", ";
			}
			return s+n;
		} else {
			return CombAlea(n-1, p);
		}
	}
}

var n0, p0, table=null;

function lire() {
	var r, u = document.frm2.t.value;
	u = u.replace(/[\,\s\;]+/g," ");
	u = u.replace(/^\s+/,"");
	u = u.replace(/\s+$/,"");
	u = u.replace(/^\s+/,"");
	if(table != null) delete(table);
	table = u.split(/\s+/g);
	n0=0;
	p0=0;
        if(table.length>=2) {
          p0=parseInt(table[1])
	} 
        if(table.length>=1) { 
           n0=parseInt(table[0]);
	}
}

function cherche() {
	nbre();
	var t = table;
	if(t.length<2) {
	  r="";
	}else {
	  //r = CombAlea(n0, p0);
	    var N = Math.floor(binom(n0,p0)*Math.random());
	    document.frm2.num.value=N;
	    r = CombN(n0, p0, N);
	}
        if(p0>0 && r=="")
           document.frm2.nar.value = "Pas de combinaison";
        else
	  document.frm2.ar.value = "{"+r+"}";
}

function nbre() {
	lire();
	document.frm2.nb.value = binom(n0, p0);
}
function efface() {
	document.frm2.t.value="";
	document.frm2.ar.value="";
}

function ncherche() {
/*
        nbre();
        if(table.length<2) {
          r="";
        }else {
	  var N = parseInt(document.frm2.num.value);
          r = CombN(n0, p0, N);
        }
        document.frm.nar.value = r;
*/
	suivte(0);
}

function CombN(n, p, N) {
        if (p<=0 || p>n || N<0 || N>= binom(n,p)) {
                return "" // l'ensemble vide
        } else {
                var a = binom(n-1,p-1)
                if(N< a) {
                        var s = CombN(n-1, p-1, N);
                        if(s != "") {
                                s +=", ";
                        }
                        return s+n;
                } else {
                        return CombN(n-1, p, N-a);
                }
        }
}

function CombAleaN(n, p) {
	var N = Math.floor(binom(n,p)*Math.random());
	return CombN(n, p, N);
}

function suivte(k) {
        nbre();
        if(table.length<2) {
          r="";
        }else {
	  var a = binom(n0, p0);
          var N = (parseInt(document.frm2.num.value)+k+a)%a;
	  document.frm2.num.value=N;
          r = CombN(n0, p0, N);
        }
	if(p0>0 && r=="")
	   document.frm2.ar.value = "Pas de combinaison";
	else
        document.frm2.ar.value = "{"+r+"}";
}