fannkuch

#{
    The Great Computer Language Shootout
http://shootout.alioth.debian.org/

contributed by Isaac Gouy
#}

routine  fannkuch(  n  :  int  )  =>  int
{
     check  =  0;
     perm  =  [  0  :  n  ];
     perm1  =  [  0  :  n  ];
     count  =  [  0  :  n  ];
     maxPerm  =  [  0  :  n  ];
     maxFlipsCount  =  0;
     m  =  n  -  1;
     r  =  n;
     while  (1)  {
          # write-out the first 30 permutations
          if  (check  <  30){
               for(i=0;  i<n;  i++)  stdio.print(  perm1[i]  +  1  );
               stdio.println();
               check++;
          }
          while  (r  !=  1){  count[r-1]  =  r;  r--;  }
          if  (  perm1[0]  &&  perm1[m]  !=  m  ){
               perm[]  =  perm1;
               flipsCount  =  0;
               while  (  k  :=  perm[0]  )  {
                    k2  =  (k+1)  >>  1;
                    for(i=0;  i<k2;  i++)  {
                         temp  =  perm[i];  perm[i]  =  perm[k-i];  perm[k-i]  =  temp;
                    }
                    flipsCount++;
               }

               if  (flipsCount  >  maxFlipsCount)  {
                    maxFlipsCount  =  flipsCount;
                    maxPerm[]  =  perm1;
               }
          }
          # Use incremental change to generate another permutation
          while  (1)  {
               if  (r  ==  n)  return  maxFlipsCount;
               perm0  =  perm1[0];
               i  =  0;
               while  (i  <  r)  {
                    j  =  i  +  1;
                    perm1[i]  =  perm1[j];
                    i  =  j;
               }
               perm1[r]  =  perm0;
               count[r]  =  count[r]  -  1;
               if  (count[r]  >  0)  break;
               r++;
          }
     }
     return  maxFlipsCount;
}

routine  main(  n  =  7  )
{
     stdio.printf("Pfannkuchen(%i) = %i\n",  n,  fannkuch(n));
}