/*  comb.js
	tout petits calculs de combinatoire, de probas et de stats
	
	Copyright (C) 2006 Jean-Paul Davalan 
	
	aucune garantie n'est donnée sur l'exactitude des résultats
	usage réservé aux pages du site "jeux et mathématiques"
	page http://jeux-et-mathematiques.davalan.org/mots/comb/index.html
	où chez les autres hébergeurs du site (orange par exemple)
	     http://perso.orange.fr/jean-paul.davalan/mots/comb/index.html

	si l'un des sites fait défaut, essayez un autre

*/

/* le fameux Cnp, coefficient du binôme de Newton, 
	nombre de sou-ens. de p éléments d'un ens de n élémts

	Cnp = n!/(p! (n-p)!) = n*(n-1)*...*(n-p+1)/p!
		= (...((n/1 * (n-1))/2 ) * (n-2)/3) *...*(n-p+1)/p
*/
function binomial(n, p) {
	if(n<0 || p<0 || p>n) 
		return 0;
	if(p==0||p==n) 
		return 1;
	if(p>n-p) 
		return binomial(n, n-p);
	var cnp=1;
	for(var i=0; i<p; i++) {
		cnp *= (n-i);
		cnp /= (i+1);
	}
	return cnp;
}
var nbcombinaisons=binomial
var cnp=binomial;

/*
	le Anp qui semble tombé dans l'oubli
	nombre d'arrangements
	Anp = n*(n-1)*...*(n-p+1)
	on a Anp = p! * Cnp  = n! / (n-p)!
*/
function nbarrangements(n, p) {
	if(n<0||p<0||p>n) 
		return 0;
	var anp=1;
	for(var i=0; i<p; i++) {
                anp *= (n-i);
        }
	return anp;
}

function nbarrangementsrepetitions() {
	var l=arguments.length, n=0, p=1;
	for(var i=0; i<l; i++) n += arguments[i];
	var m=n;
	for(var i=0; i<l; i++) {
		for(var j=1; j<=arguments[i]; j++) {
			p *= m;
			p /= j;
			m--;
		}
	}
	return p;
}
var Arepet = nbarrangementsrepetitions;

function nbcombinaisonsrepetitions(n, k) {
	return binomial(n+k+1,k-1);
}

var Crepet = nbcombinaisonsrepetitions;

function factorielle(n) {
	var fc=1;
	for(i=1;i<=n;i++) fc *= i;
	return fc;
}
var fact = factorielle;
var nbpermutations=factorielle;

function stats1(liste) {
	var s=0, s2=0, n=0;
	for(i=0; i<liste.length; i++) {
		if(liste[i]!=null) {
			liste[i]= (liste[i]+"").replace(/\s+/g,"")
			if(liste[i]!="") {
				liste[i] = parseFloat(liste[i]);
				s += liste[i];
				s2 += liste[i]*liste[i];
				n++;
			} else return null;
		}
	}
	if(n==0) return null;
	var moyenne=s/n;
	var variance=s2/n-moyenne*moyenne;
	var ecarttype=Math.sqrt(variance);
	return {moyenne:moyenne, n:n, variance:variance, ecarttype:ecarttype, somme:s, somme2:s2}
}

function stats2(listeX, listeY) {
	var xstats = stats1(listeX), ystats = stats1(listeY);
	var n=0, sxy=0, correlation, covariance;
	if(xstats==null || ystats==null ||xstats.n==0 || ystats.n==0 || xstats.n!=ystats.n) return null;
	for(var i=0; i<listeX.length; i++) {
		sxy += parseFloat(listeX[i])*parseFloat(listeY[i]);
		n++;
	}
	covariance = sxy/n - xstats.moyenne * ystats.moyenne
	correlation = covariance/(xstats.ecarttype*ystats.ecarttype);
	return {moyenneX:xstats.moyenne, varianceX:xstats.variance, ecarttypeX:xstats.ecarttype, 
	sommeX:xstats.somme, somme2X:xstats.somme2, moyenneY:ystats.moyenne, varianceY:ystats.variance, 
	ecarttypeY:ystats.ecarttype, sommeY:ystats.somme, somme2Y:ystats.somme2, n:n, covariance:covariance, 
	correlation:correlation};
}

/*
 // # ci-dessous pour essais en ligne de commande, faire dans un shell
 // cat comb.js | js
 // le print permet alors l'écriture dans le terminal, tandis que dans une page web
 // il provoque l'impression
var lx=[1,2,3,4,5,6,7,8,9], ly=[9,8,7,6,5,4,3,2,1];
var r = stats2(lx, ly);
print(r.correlation)
print(r.covariance)
print (r.moyenneX)
*/

/* produit de plusieurs listes 
    var L = produit(L1, L2, L3, ..., Ln)
*/
function produitL() {
	if(arguments.length==0) return null;
	var X=[];
	for(var i=0; i<arguments[0].length; i++) 
		X[i]=arguments[0][i];
	for(var j=1; j<arguments.length; j++) {
		if(arguments[0].length!=arguments[j].length) 
			return null;
		for(var i=0; i<arguments[0].length; i++)
			X[i] *=arguments[j][i];
	}
	return X;
}

function mapL(L, f) {
	if(L==null || f==null) return null;
	var U = [];
	try {
		for(var i=0; i<L.length; i++) {
			U[i] = f(L[i]);
		}
	}
	catch(err) { return null;}
	return U;
}


var comb_resultats="";

function affiche() {
	for(var i=0; i<arguments.length; i++)
		comb_resultats += arguments[i];
}
function affichel() {
	for(var i=0; i<arguments.length; i++)
		comb_resultats += arguments[i];
	comb_resultats += "\n"
}
var afficheNL = affichel;

function efface() {
  document.frm.ar.value="";
}
function effectue() {
	comb_resultats=""
	var s = document.frm.ar.value
	var stab = s.split(/#\s*\-{10,}/g)
	var st = stab[0];
	st = st.replace(/[\s\n]+$/,"");
	st = st.replace(/^[\n]+/,"");
		var z=eval(st);
	document.frm.ar.value = st+"\n# -----------------------\n"+comb_resultats;
}


function varalea() {
	this.type="varalea";
	this.X = [];
	this.p = [];
	this.proba = [];
	this.n=0;
	this.somme=0,
	this.somme2=0;
	this.effectifs=0;

	this.init = function(L, p) {
		//if(L==null || p==null || L.length != p.length) return null;
		this.n=L.length;
		this.effectifs = 0;
		for(var i=0; i<this.n; i++) {
			this.X[i] = parseFloat(L[i]);
			this.p[i] = parseFloat(p[i]);
			this.somme +=this.X[i]*this.p[i];
			this.somme2 += this.X[i]*this.X[i]*this.p[i];
			this.effectifs += this.p[i];
		}
		for(var i=0; i<this.n; i++) {
			this.proba[i] = this.p[i]/this.effectifs;
		}
		this.moyenne= this.somme/this.effectifs; 
		this.esperance=this.moyenne;
		this.variance = this.somme2/this.effectifs - this.moyenne*this.moyenne;
		this.ecarttype=Math.sqrt(this.variance);
		this.ecartype=this.ecarttype;
	}

	this.oper = function(op, V) {
		var V2 = new varalea();
		var X = new Array();
		var P = new Array();
		for(var i=0; i<this.n; i++) {
			for(var j=0; j<V.n; j++) {
				var u = (op=="mult")?this.L[i]*V.L[j]: this.L[i]+V.L[j];
				if(X[u]==null) {
					X[u]=0;
				}
				X[u] += this.p[i]*V.p[j];
			}
		}
		var k=0;
		var L1=new Array(),p1=new Array();
		for(u in X) {
			L1[k]=u
			p1[k]=X[u];
			k++;
		}
		V2.init(L1, p1);
		return V2;
	}
	this.mult = function(V) {
		return oper("mult", V);
	}
	this.add = function(V) {
                return oper("add", V);
        }

	this.clone = function() {
		var V2 = new alea();
		var L2 = [], p2=[];
		for(var i=0; i< this.n; i++) {
			L2[i] = this.L[i]
			p2[i] = this.p[i]
		}
		V2.init(L2, p2);
		return V2;
	}

	this.map = function(f) {
		var V2=new alea();
		var L2 = [], p2=[];
		var k=0;
		var rg=[];
                for(var i=0; i< this.n; i++) {
                        var a = f(this.L[i])
                        if(rg[a]==null) {
				rg[a]=k;
				p2[k]=this.p[i]
				L2[k]=a;
			} else {
				p2[rg[a]] += this.p[i];
			}
		}
		for(var i=0; i<L2.length-1; i++) {
			for(var j=i+1; j<L2.length-1; j++) {
				if(L2[j]<L2[i]) {
					//[L2[j], L2[i]] = [L2[i], L2[j]]
					var u = L2[j];
					L2[j]=L2[i];
					L2[i]=u;
					// [p2[j], p2[i]] = [p2[i], p2[j]]
					var v = p2[j];
					p2[j]=p2[i];
					p2[i]=v;
				}
			}
		}
		V2.init(L2,p2)
                return V2;
        }

}
var seriestat=varalea;

function ensemble() {
	this.type="ensemble";
	this.el=[];
	this.rg=[]
	this.str=null;
	this.init = function() {
		for(var i=0; i< arguments.length; i++) {
			var x = arguments[i];
			if(typeof x == 'number' ||typeof x == 'string') {
				if(this.el.length==0||this.rg[x]==null) {
					this.rg[x]=this.el.length;
					this.el[this.el.length]=x;
				}
			} else if (typeof x == 'object') {
				for(var j=0; j<x.length; j++) {
					var y=x[j];
					if(typeof y=='number' || typeof y=='string') {
						if(this.rg[y]==null) {
							this.rg[y]=this.el.length;
							this.el[this.el.length]=y;
						}
					}
				}
			}
		}
		this.card = this.el.length;
	}
	if(arguments.length>0) {
		for(var i=0; i<arguments.length; i++) {
			this.init(arguments[i]);
		}
	}

	this.inter = function() {
		var ens = new ensemble();
		for(var i=0; i<this.el.length; i++) {
			var x = this.el[i]
			var test = true
			for(var j=0; j< arguments.length; j++) {
				u = arguments[j];
				if(u.rg[x]==null) {
					test=false
					break;
				}
			}
			if(test==true) ens.init(x);
		}
		return ens;
	}
	this.diff = function() {
		var ens = new ensemble();
		for(var i=0; i<this.el.length; i++) {
			var x = this.el[i]
			var test = true
			for(var j=0; j< arguments.length; j++) {
				u = arguments[j];
				if(u.rg[x]!=null) {
					test=false
					break;
				}
			}
			if(test==true) ens.init(x);
		}
		return ens;
	}
	this.union = function() {
		var ens = new ensemble();
		ens.init(this.el)
		for(var i=0; i<arguments.length; i++) {
			var u = arguments[i];
			ens.init(u.el)
		}
		return ens
	}
	this.delta = function() {
		var ens=new ensemble();
		ens.init(this.el);
		for(var i=0; i< arguments.length;i++) {
			var ens0 = ens.union(arguments[i]), ens1=ens.inter(arguments[i]);
			delete(ens)
			ens = ens0.diff(ens1);
		}
		return ens;
	}
	this.permute = function() {
		var t = [], n= this.el.length
		for(var i=0; i<n; i++) 
			t[i] = this.el[i];
		for(var i=n-1; i>0; i--) {
			var j=Math.floor((i+1)*Math.random());
			if(i!=j) {
				//[t[i],t[j]]=t[j],t[i]]
				var c=t[i];t[i]=t[j];t[j]=c;
			}
		}
		var s="[";
		var m = n;
		if(arguments !=null && arguments.length==1) {
			m = parseInt(arguments[0]);
			if(m<0 || m>n) return ".";
			if(m==0 ) return "[]";
		} else {
			m=n;
		}
		for(var i=0;i<m; i++) {
			s+=t[i]
			if(i==m-1) s+="]"
			else s+=", "
		}
		return s;
	}
	this.arrange=this.permute;
	this.sousensemble = this.combinaison = function() {
		var n=this.el.length;
		var res=""
		if(arguments!=null && arguments.length > 0) {
			for(var i=0; i<arguments.length; i++) {
				var m=parseInt(arguments[i]);
				if(m<0 || m>n) {
					s = "."
				} else if (m==0) {
					s = "[]"
				} else {
					var g=eval(this.permute(m));
					var h = []
					for(var j=0; j< g.length;j++) 
						h[g[j]]=1;
					s=""
					for(var k=0; k<n; k++) {
						if(h[this.el[k]]!=null) 
							s += ((s=="")?"[":", ")+this.el[k]
					}
					s += "]";
				}
				
				res += s + ((i==0)?"":", ");
			}
		}
		return res
	}
	this.tostring = function() {
		if(this.str != null) return this.str;
		var s ="["
		var pre = ""
		for(var x in this.rg) {
			s += pre+x
			pre=", "
		}
		s += "]"
		this.str=s;
		return s;
	}
	this.egale=function(b) {
		if(this.el.length != b.el.length) return false;
		for(var i=0; i<this.el.length;i++) {
			if(b.rg[this.el[i]]==null) return false;
		}
		return true;
	}
	this.inclus=function(b) {
		if(this.el.length > b.el.length) return false;
		for(var i=0; i<this.el.length;i++) {
			if(b.rg[this.el[i]]==null) return false;
		}
		return true;
	}
}
function typede(x) {
	if(typeof x == 'object') {
		if(x != null && x.type !=null) {
			return x.type;
		} else {
			return 'object';
		}
	}
	return '';
}