/* dup.js (down-up permutations : dup)   
   http://perso.wanadoo.fr/jean-paul.davalan/mots/comb/perm/dup.js
   http://perso.wanadoo.fr/jean-paul.davalan/mots/comb/perm/ud.html

   
   Copyright (C) 2003-2004 Jean-Paul Davalan <jpdvl@wanadoo.fr>
   http://perso.wanadoo.fr/jean-paul.davalan

   page :
   http://perso.wanadoo.fr/jean-paul.davalan/index.html
   détermination de toutes les 
   Permutations OU dérangements OU down-up OU up-down
   de l'ensemble [n] = {1,2,...,n} des n entiers naturels
   de 1 à n.

   exemple : 
   213564 représente la permutation 
   1 -> 2  
   2 -> 1    (1 2)   est un cycle
   3 -> 3    (3)     est un point fixe
   4 -> 5
   5 -> 6
   6 -> 4    (4 5 6) est un autre cycle

   Une autre notation est (1 2) (3) (4 5 6)

 */
   
// 0 : toutes, 1 : down-up, 2 : up-down, 3 :  dérangement
var permut = 1;
var chaine;

// teste si la permutation est bien down-up (ou up-down)
function test(t, k, j, a) {
  if(permut==0 || permut==3 ) return true;
  if(permut==1 && (( k%2==0 && t[j]<a) || (k%2==1 && t[j]>a))) return true;
  if(permut==2 && (( k%2==0 && t[j]>a) || (k%2==1 && t[j]<a))) return true;
  return false;
}

// récursivement détermine les permutations et les affiches lorsqu'elles
// sont complètes
// au début : 1 2 3 4 5 ... n et on choisit l'image de 1 (parmi 1 2 ... n)
// si, par exemple,  1 a pour image 4 on échange ainsi
//            4 2 3 1 5 ... n
// ensuite on cherche l'image de 2 parmi 2 3 1 5 ... n, par exemple 5
//            4 5 3 1 2 ... n   et on échange 2 et 5 et ainsi de suite
function perm(n, t, k) {
//if (k==2) alert("perm");
  if(limite>0 && nbre>=limite) {
    return;
  }
  var a, r, j, i, tb=new Array();
  if(k==1) {
    for(j=1;j<=n;j++) {
      for(i=1;i<=n;i++) 
        tb[i]=i;
      tb[1]=j;
      tb[j]=1;
      if(permut !=3 || j > 1)
        perm(n, tb, 2);
    }
  } else if(k>1 && k<=n) {
    a = t[k-1];
    for(j=k;j<=n;j++) {
      if(test(t, k, j, a)==true) {
         for(r=1;r<=n;r++)
	   tb[r]=t[r];
	 if(j>k) {
	   tb[k] = t[j];
	   tb[j] = t[k];
	 }
	 if(permut != 3 || tb[j] != j)
	   perm(n, tb, k+1);
      }
    }
  } else {
    var s= " "+bij(t, n)+" ;";
    if(s.length >25)
      s += "\n    "+ cycles(t, n)+ "\n";
    else
      s += "   "+ cycles(t, n)+ "\n";
    chaine += s;
    nbre++;
  }
}
function bij(t, n) {
  var s="", i;
  for(i=1;i<=n;i++) {
    s += t[i];  
    if(i < n) s += " ";
  }
  return s;
}

function cycles(t, n) {
  if(document.frm.c.checked==false) return "";
  var s="", cy=0, l=0, der=true, i, j, k, tb = new Array();
  for(i=1; i <= n; i++) 
    tb[i]=true;
  for(i=1; i<=n; i++) {
    if(tb[i]==true) {
      cy++;
      j=1;
      k=i; 
      s += "("+k; 
      tb[k]=false;
      while(t[k] != i) {
        j++;
        k = t[k];
	s += " "+k;
	tb[k]=false;
      }
      if(j>l) l=j;
      if(j==1) 
        der = false;
      s += ")";
    }
  }
  if(cy>1) s = cy+" cycles : "+s;
  else     s = "1 cycle : "+s;
  if(l<3) {
    s += " invol.";
    ninvol++;
  }
  if(der==true) {
    s += " dergt.";
    ndergt++;
  }
  return s;
}

    
var limite=20; // affichage limite
var nbre;      // nbre de permutations trouvées
var ninvol, ndergt;

function cherche() {
  var n;
  document.frm.ar.value="";
  var uu = new Array();
  var ds, dt = document.frm.n.value;
  do  {
    ds = dt;
    dt = ds.replace(/\s+/g," ");
    dt = dt.replace(/\s*[,;:]+\s*/g,",");
    dt = dt.replace(/[,]+/g,",");
    dt = dt.replace(/[,]+/g," ,");
  }while (ds!=dt);
  document.frm.n.value=dt;
  uu = dt.split(/[,]/);
 
  for (var ui=0; ui< uu.length;ui++) {
  //alert(uu[ui])
  var u = uu[ui].split(/\s+/);
  var t=new Array();
  var n0=parseInt(u[0]);
  var n1 = n0;
  if(document.frm.rd[0].checked==true) permut=0;
  else if (document.frm.rd[2].checked==true) permut=1;
  else if (document.frm.rd[3].checked==true) permut=2;
  else if (document.frm.rd[1].checked==true) permut=3;
  var lm, ll = document.frm.l.value;
  do {
    lm=ll;
    ll=lm.replace(/\s+/g,"");
  }while (ll!=lm);
  if(ll==void(0) || ll=="" || ll=="infty") limite=0;
  else limite = parseInt(ll);
  if(u.length==2)
    n1=parseInt(u[1]);
//  document.frm.ar.value="";
  if(ui==0) {
  if(permut==0) document.frm.ar.value="Permutations quelconques\n";
  else if(permut==3) document.frm.ar.value="Dérangements\n";
  else if(permut==1) document.frm.ar.value="Permutations down-up (alternantes)\n";
  else if(permut==2) document.frm.ar.value="Permutations up-down\n";
  }
  for(n=n0; n<=n1; n++) {
   if(n==0) {
         document.frm.ar.value +="# n = 0   nbre : 1\n";
         document.frm.ar.value += "  l'unique permutation de l'ensemble vide Ø\n";
   } else {
     nbre = 0;
     ninvol= 0;
     ndergt=0;
     chaine="";
     perm(n, t, 1);
     if(limite>0 && nbre==limite)
       document.frm.ar.value +="# n = "+n+"\n";
     else {
       document.frm.ar.value +="# n = "+n+"  nbre perm. : "+nbre+"  invol. : "+ninvol+" dergt. : "+ndergt+"\n";
     }

     document.frm.ar.value += chaine;
     if(limite>0 && nbre==limite)
       document.frm.ar.value += "# limite "+limite+"\n";
   }
  }
  }
}

function demo(n, type, c, lim) {
  if(c=="cycles") document.frm.c.checked = true;
  else document.frm.c.checked=false;
  document.frm.n.value = n;
  if(type=="perm") document.frm.rd[0].checked=true;
  else if(type=="der") document.frm.rd[1].checked=true;
  else if (type=="up") document.frm.rd[2].checked=true;
  else if (type=="down") document.frm.rd[3].checked=true;
  document.frm.l.value = lim;
  document.frm.ar.value=" ";
  // temporisation !!!! (mozilla 1.5 workaround)
  // Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.5) Gecko/20031007
  for(i=1;i<10000;i++) u=0; // inutile sous konqueror
  cherche();
}