function permute(t,a,k) {
	var i, x;
	for(i=k-1;i>0;i--) {
		j=Math.floor((1+i)*Math.random());
		if(j!=i) {
			x=t[a+i];
			t[a+i]=t[a+j];
			t[a+j]=x;
		}
	}
	
}
/* un cycle  a-> b ->c ... -> d et retour -> a */
function cycle() {
	this.n=1
	this.l=[];  // liste des elmts
	this.t=[];  // this[elmt] = elmt suivant
	if(argument[0]!=null)
		this.n=parseInt(argument[0]);
	// l est un tableau
	this.fromListe = function(l) {
		var i;
		this.n=l.length
		for(i=0;i<this.n;i++) 
			this.l[i]=l[i]
		for(i=0;i<this.n-1;i++) 
			this.t[this.l[i]]=this.l[i+1]
		this.t[this.l[this.n-1]]=this.l[0];  // retour
	}
	this.image = function(x) {  // image par la fonction
		return this.t[x]
	}
}
function cmpare(a, b) {
	return (parseInt(a)<=parseInt(b))? -1 : 1;
}

function perm() {
	this.n=0;
	this.t=new Array();
	this.matr=[];

	this.sdiag=""; // chaîne
	this.sadiag=""
	this.diag=[];
	this.adiag=[]

	this.sdiagtri=""; // chaîne
        this.sadiagtri=""
        this.diagtri=[];
        this.adiagtri=[]


	this.ncycles=0; // nb de cycles
	this.cycles=[]; // les cycles de la permutation

	this.dId="";

	if(arguments[0]!=null)
		this.n=parseInt(arguments[0]);

	this.auhasard = function() {
		var i, j;	
		for(i=1;i<=this.n;i++)
			this.t[i]=i
		permute(this.t,1,this.n);
	}

	this.fromtable = function(m,k,t) {
		var i;
		this.n = m*k;
		for(i=1; i<=this.n; i++) {
			this.t[i]=t[i];
		}
	}
	/* permutation aléatoire à partir de la liste des longueurs de cycles */
	this.diffId = function() {
		var i, ta = [];
		for(i=1; i<=this.n; i++) {
			ta[i-1]=this.t[i]-i;
		}
		ta.sort(cmpare);
		var s="";
		for(i=1; i<=this.n; i++) {
			s += ta[i-1];
			if(i<this.n) s += " "
		}
		this.dId = s;
	}
	
	this.cyclesAleatoires = function(s) {
		var i,j,u=s+"";
		u = u.replace(/^\s+/,"");
		u = u.replace(/\s+$/,"");
		u = u.replace(/[\s\n\,\;\:]+/g," ");
		var v=u.split(/\s+/g);
		this.n=0;
		for(i=0; i<v.length; i++) {
			v[i]=parseInt(v[i])
			this.n += v[i];
		}
		var tb=[];
		for(i=1;i<=this.n;i++) tb[i]=i;
		var pos=1;
		permute(tb, 1, this.n)
		for(i=0;i<v.length; i++) {
			for(j=0;j<v[i]-1;j++) {
				this.t[tb[pos+j]]=tb[pos+j+1]
			}
			this.t[tb[pos+v[i]-1]]=tb[pos]
			pos += v[i]
		}
	}
	this.fmatr = function () {
		var i;
		for(i=1; i<= this.n; i++) {
			this.matr[i]=[]
			for(j=1; j<=this.n; j++) {
				this.matr[i][j]=0
			}
			this.matr[i][this.t[i]]=1
		}
	}
	/* calcule les sommes sur les diagonales */
	this.fdiags = function() {
		for(i=0; i<2*this.n-1;i++) {
			this.diag[i]=this.adiag[i]=0;
		}
		for(i=1; i<=this.n; i++) {
			j=this.t[i];
			this.diag[this.n+j-i-1] += 1
			this.adiag[i+j-2] += 1;
		}
		for(i=0; i<2*this.n-1; i++) {
			this.sdiag += this.diag[i]+" ";
			this.sadiag += this.adiag[i]+" ";
		}
		for(i=0; i<2*this.n-1; i++) {
                        this.diagtri[i] = this.diag[i]
                        this.adiagtri[i] = this.adiag[i];
		}
		this.diagtri.sort(cmpare);
		this.adiagtri.sort(cmpare);
		this.sdiagtri="";
		this.sadiagtri="";
                for(i=0; i<2*this.n-1; i++) {
                        this.sdiagtri += this.diagtri[i]+" ";
                        this.sadiagtri += this.adiagtri[i]+" ";
                }
	}
	this.affiche = function() {
		var i, j, s="";
		this.fmatr();
//alert(this.n+"\n"+this.t)
		s += "<u>Permutation :</u> s = ("
		for(i=1; i<=this.n; i++)  {
			s +=this.t[i]
			if(i<this.n) s+=",&nbsp;";
		}
		s += ")<br />"
		s += "<br /><br />"
		this.diffId();

		s += '<u>Différence :</u> la différence de s et de l\'identité (1 2 3 ...) est rangée dans l\'ordre croissant<br />'+
			' d = '+this.dId+'<br />Voir le paragraphe "<a href="#SEQ">Nombre de classes</a>" <br />'

		s += "<u>Matrice :</u>"
		s += "<br />"
//		s+='<center><table class="def" id="tm" style="font-size:15px;border:1pt solid">'
		s+='<center>'
		s+='<table>'
		//ligne du haut
		s += '<tr><td><img src="arc.png" width="20" height="21" alt=" . "></td><td>'
		s+= '<table class="def" style="border:1pt solid;background-color:#ff9;color:#048;"><tr>'
		for(i=1; i<=this.n; i++) {
			s +='<td class="tm">'+i+"</td>"
		}
		s+= '</tr></table></td></tr>'
		// bas
		s += '<tr><td>'
		s+= '<table class="def" style="border:1pt solid;background-color:#ff9;color:#048;">'
		for(i=1; i<=this.n; i++) {
                        s +='<tr><td class="tm">'+i+"</td></tr>"
                }
		s += '</table></td><td>'
		s += '<table class="def" style="border:1pt solid;background-color:#a8ffb5;">'
		for(i=1; i<=this.n; i++) {
			s +="<tr>"
			for(j=1; j<=this.n; j++) {
				var ss=(this.matr[i][j]==1)?"<b>1</b>":"0"
				s +='<td class="tm">'+ss+"</td>"
			}
			s += "</tr>"
		}
		s += "</table></td></tr></table></center>"
		s+= "<u>Diagonales</u> :"+this.sdiag+"<br />"
		s+= "<u>Antidiagonales</u> :"+this.sadiag+"<br />"
		s+= "<br />"
		s+= "Rangées dans un ordre croissant<br />"
                s+= "<u>Diagonales</u> :"+this.sdiagtri+"<br />"
                s+= "<u>Antidiagonales</u> :"+this.sadiagtri+"<br />"
 

		return s;
	}
}

function chercheP() {
	var n=parseInt(document.frm.n.value);
	var p = new perm(n);
	p.auhasard();
	p.fdiags();
	var s = p.affiche();
	document.getElementById("res").innerHTML=s;
}

function chercheC() {
        var c=document.frm.c.value;
        var p = new perm();
        p.cyclesAleatoires(c);
        p.fdiags();
        var s = p.affiche();
        document.getElementById("res").innerHTML=s;
}


function prpr(s) {
//alert(s)
       var n,k,a,i,j, s1=s+"";
	s1=s1.replace(/^\s+/,"");
	s1=s1.replace(/\s+$/,"");
	s1=s1.replace(/\s+/g," ");
//alert(s1)
	var u = s1.split(/\s+/g);
//alert(u)
	var kn = u.length;
	var nb=[], or=[], t=[];

	for(i=0; i< kn;i++) {
		a = u[i];
		if(or[a]==null) {
			or[a]=i	
			nb[a]=1
		} else {
			nb[a]++;
		}
	}
	k=nb[u[0]];
	n=kn/k;
//alert(kn+" "+n+" "+k)
//alert(or)
	for(x in or) {
		x = parseInt(x)
		a=or[x]+1
		for(i=0; i<k-1; i++) 
			t[a+x*i] = a+x*i+x
		t[a+x*(k-1)]=a
	}
/*
	var st=""
	for(i=1; i<=kn; i++) {
		st += t[i]
		if(i<kn) st +=" ";
	}
*/
//	alert(st)
	var p = new perm();
	p.fromtable(n,k,t)
	p.fdiags();
        var s = p.affiche();
        document.getElementById("res").innerHTML=s;

}

function chercheR() {
	var n=parseInt(document.frm.rn.value)
	var k=parseInt(document.frm.rk.value)
	if(k<2 || k>4) return;
	var v=1000*n+k;
	document.R.rythm(v);
}