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 )
  43                                 printf("%d", (int)(1+perm1[i]));
  44             printf("\n");
  45             ++didpr;
  46         }
  47
  48         for( ; r!=1 ; --r ) {
  49             count[r-1] = r;
  50         }
  51
  52 #define XCH(x,y)        { Aint t_mp; t_mp=(x); (x)=(y); (y)=t_mp; }
  53
  54         if( ! (perm1[0]==0 || perm1[n1]==n1) ) {
  55             flips = 0;
  56             for( i=1 ; i<n ; ++i ) {    /* perm = perm1 */
  57                 perm[i] = perm1[i];
  58             }
  59             k = perm1[0];               /* cache perm[0] in k */
  60             do {                        /* k!=0 ==> k>0 */
  61                 Int     j;
  62                 for( i=1, j=k-1 ; i<j ; ++i, --j ) {
  63                     XCH(perm[i], perm[j])
  64                 }
  65                 ++flips;
  66                 /*
  67                  * Now exchange k (caching perm[0]) and perm[k]... with care!
  68                  * XCH(k, perm[k]) does NOT work!
  69                  */
  70                 j=perm[k]; perm[k]=k ; k=j;
  71             }while( k );
  72
  73             if( flipsMax < flips ) {
  74                 flipsMax = flips;
  75             }
  76         }
  77
  78         for(;;) {
  79             if( r == n ) {
  80                 return flipsMax;
  81             }
  82             /* rotate down perm[0..r] by one */
  83             {
  84                 Int     perm0 = perm1[0];
  85                 i = 0;
  86                 while( i < r ) {
  87                     k = i+1;
  88                     perm1[i] = perm1[k];
  89                     i = k;
  90                 }
  91                 perm1[r] = perm0;
  92             }
  93
  94             if( (count[r] -= 1) > 0 ) {
  95                 break;
  96             }
  97             ++r;
  98         }
  99     }
 100 }
 101
 102 int
 103 main( int argc, char* argv[] )
 104 {
 105     int         n = (argc>1) ? atoi(argv[1]) : 10;
 106
 107     printf("Pfannkuchen(%d) = %ld\n", n, fannkuch(n));
 108     return 0;
 109 }