nsz Git - libfirm/blob - ir/be/test/langshootout/fannkuch.c

   1 /*
   2  * The Computer Lannguage Shootout
   3  * http://shootout.alioth.debian.org/
   4  * Contributed by Heiner Marxen
   5  *
   6  * "fannkuch"   for C gcc
   7  *
   8  * $Id$
   9  */
  10
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13
  14 #define Int     int
  15 #define Aint    int
  16
  17     static long
  18 fannkuch( int n )
  19 {
  20     Aint*       perm;
  21     Aint*       perm1;
  22     Aint*       count;
  23     long        flips;
  24     long        flipsMax;
  25     Int         r;
  26     Int         i;
  27     Int         k;
  28     Int         didpr;
  29     const Int   n1      = n - 1;
  30
  31     if( n < 1 ) return 0;
  32
  33     perm  = calloc(n, sizeof(*perm ));
  34     perm1 = calloc(n, sizeof(*perm1));
  35     count = calloc(n, sizeof(*count));
  36
  37     for( i=0 ; i<n ; ++i ) perm1[i] = i;        /* initial (trivial) permu */
  38
  39     r = n; didpr = 0; flipsMax = 0;
  40     for(;;) {
  41         if( didpr < 30 ) {
  42             for( i=0 ; i<n ; ++i ) printf("%d", (int)(1+perm1[i]));
  43             printf("\n");
  44             ++didpr;
  45         }
  46         for( ; r!=1 ; --r ) {
  47             count[r-1] = r;
  48         }
  49
  50 #define XCH(x,y)        { Aint t_mp; t_mp=(x); (x)=(y); (y)=t_mp; }
  51
  52         if( ! (perm1[0]==0 || perm1[n1]==n1) ) {
  53             flips = 0;
  54             for( i=1 ; i<n ; ++i ) {    /* perm = perm1 */
  55                 perm[i] = perm1[i];
  56             }
  57             k = perm1[0];               /* cache perm[0] in k */
  58             do {                        /* k!=0 ==> k>0 */
  59                 Int     j;
  60                 for( i=1, j=k-1 ; i<j ; ++i, --j ) {
  61                     XCH(perm[i], perm[j])
  62                 }
  63                 ++flips;
  64                 /*
  65                  * Now exchange k (caching perm[0]) and perm[k]... with care!
  66                  * XCH(k, perm[k]) does NOT work!
  67                  */
  68                 j=perm[k]; perm[k]=k ; k=j;
  69             }while( k );
  70             if( flipsMax < flips ) {
  71                 flipsMax = flips;
  72             }
  73         }
  74
  75         for(;;) {
  76             if( r == n ) {
  77                 return flipsMax;
  78             }
  79             /* rotate down perm[0..r] by one */
  80             {
  81                 Int     perm0 = perm1[0];
  82                 i = 0;
  83                 while( i < r ) {
  84                     k = i+1;
  85                     perm1[i] = perm1[k];
  86                     i = k;
  87                 }
  88                 perm1[r] = perm0;
  89             }
  90             if( (count[r] -= 1) > 0 ) {
  91                 break;
  92             }
  93             ++r;
  94         }
  95     }
  96 }
  97
  98 int
  99 main( int argc, char* argv[] )
 100 {
 101     int         n = (argc>1) ? atoi(argv[1]) : 10;
 102
 103     printf("Pfannkuchen(%d) = %ld\n", n, fannkuch(n));
 104     return 0;
 105 }