function factor(n) {
   this.n = n;
   this.g = new Array(this.n);
   this.a=1;
   this.b=2;
   this.fail=false;
   this.s = "";
   this.nsols=0;
   this.p=false;
   this.ps="";

   function affiche() {
      this.s =  "notations\n"
               +"   i)       : couleur des arêtes ou n° du 1-facteur\n"
               +"   [x -- y] : arête de couleur i ou arête du 1-facteur\n"
               +"------------------------------------------------------\n";
      for(var k=1; k< this.n; k++) {
        this.s +=k+" )  ";
        for(var i=0; i< this.n-1; i++) {
          for(var j=i+1; j<this.n;j++) {
            if(this.g[i][j]==k) {
              if(i<j)
                 this.s += "["+i+" -- "+j+"] ";
              else
                 this.s += "["+j+" -- "+i+"] ";
            }
          }
        }
        this.s += "\n";
      }
    }
    this.affiche=affiche;

    function teste() {
       var i, u=this.g[this.a][this.b];
       for(var i=0;i< this.a;i++) {
          if(this.g[i][this.a]==u) {
             return false;
          }
       }
       for(i=0;i< this.a;i++) {
         if( this.g[i][this.b] == u) {
            return false;
         }
       }
       for(i=this.a+1;i< this.b;i++) {
           
          if(this.g[this.a][i] == u) {
             return false;
          }
       }
       return true;
    }
    this.teste=teste;

    function suivte() {
       var u= this.a, v=this.b+1;
       if(v >= this.n) {
         u++;
         v=u+1;
         if(u>= this.n-1) {
           this.nsols++;
           this.affiche();
           // on reste à la même place
           return true;
         }
       }
       this.a=u;
       this.b=v;
       this.g[this.a][this.b] = 0;
       return false;
    }
    this.suivte=suivte;

    function prec() {
      this.g[this.a][this.b] = 0;
      var u = this.a, 
          v = this.b-1;
      if(v <= this.a) {
         u = this.a-1;
         v= this.n-1;
         if(u==0) {
           this.s = "Recommencez ("+this.nsols+" solutions trouvées)\n";
           this.fail=true;
           return true;
         }
      }
      this.a=u;
      this.b=v;
      return false;
    }
    this.prec=prec;

    function init() {
      if(this.n<4) return;
      var essais = 3;
      if(this.n==4) essais=1;
      else if(this.n>8) essais=10;
      var verif=true;
      for(this.a=1; verif && this.a<this.n-1; this.a++) {
         for(this.b=this.a+1; verif && this.b<this.n; this.b++) {
            verif=false;
            for(var i=0; !verif && i<essais; i++) {
               this.g[this.a][this.b]  = Math.floor(1+(this.n-1)*Math.random());
               verif= this.teste();
            }
         }
      }
    }
    this.init=init;

    function f() {
      
      for(var i=0; i<this.n; i++)
        this.g[i] = new Array(this.n);

   // précoloriage des arêtes 0-j de la couleur j
      for(var j=1;j< this.n;j++) {
           this.g[0][j]=j;
      }
      if(this.n==2) {
        this.affiche();
        return;
      }
      this.init();
      while(true) { 
        do {
          this.g[this.a][this.b] += 1;
    	} while(this.g[this.a][this.b] <= this.n-1 && this.teste()==0);
	if(this.g[this.a][this.b] <= this.n-1) {
            var r = this.suivte();
            if(r) return; 
	} else {
            var r = this.prec();
            if(r) return;
        }
      }
      //printf("Nb solutions %d\n",nsols);
    }
    this.f=f;
    
    function hamil(x, y) {
	var k=0, m=0, ens=new Array(), liste=new Array();
        for(var i=0; i<this.n; i++) ens[i]=false;
        ens[0]=true;
        liste[k]=0;k++;

        do {
           test=false;
           var m0=k;
           for(var t=m; t<m0; t++) {
              i=liste[t];
             for(j=0;j<i;j++) {
               if(ens[j]==false && (this.g[j][i]==x || this.g[j][i]==y)) {
                  liste[k]=j; k++;
                  ens[j]=true;
                  test=true;
               }
             }
             for(j=i+1;j<this.n;j++) {
               if(ens[j]==false && (this.g[i][j]==x || this.g[i][j]==y)) {
                  liste[k]=j;
                  k++;
                  ens[j]=true;
                  test=true;
               }
             }
           }
           m=m0;
         }while(test);
         if(k==this.n) return true;
         else return false;
      }
      this.hamil=hamil;

      function perfect() {
         var res=true;
         var u="", v="";
         var perf= new Array(this.n);
         for(var j=1; j<this.n;j++)
            perf[j]=new Array(this.n);
         for(var i=1; i<this.n;i++) {
           for(var j=i+1; j<this.n; j++) {
               perf[i][j]=this.hamil(i,j);
               var z="("+i+", "+j+") ";
               if(perf[i][j]==false) {
                 res=false;
                 v += z;
               } else {
                 u += z;
               }
           }
         }
         this.p = res;
         var s="";
         if(res) s = "La 1-factorisation est parfaite\n";
         else {
            s = "les paires de 1-facteurs donnant un cycle hamiltonien sont\n";
            s += u+"\n";
            s += "les paires de 1-facteurs sans cycle hamiltonien sont\n";
            s += v;
         }
         this.ps=s;
         return s;
      }
      this.perfect=perfect;

}
	
function cherche2() {
  document.frm2.a.value ="";
  var n = parseInt(document.frm2.n.value);
  n += n%2
  document.frm2.n.value=n;
  var fc;
  do {
  if(fc)delete(fc);
  fc = new factor(n);
  fc.f();
  } while(fc.fail==true);
  var s = fc.perfect();
  document.frm2.a.value = fc.s+"\n"+s;
}

function chperf() {
  document.frm2.a.value ="";
  var n = parseInt(document.frm2.n.value);
  n += n%2
  document.frm2.n.value=n;
  var fc=null;
  do {
    delete(fc);
    fc = new factor(n);
    fc.f();
    fc.perfect();
  }while(fc.p==false);
  document.frm2.a.value = fc.s+"\n"+fc.ps;
}

function efface2() {
  document.frm2.a.value ="";
  document.frm2.n.value ="";
}