htswanalysis/MACS/lib/gsl/gsl-1.11/permutation/test.c

   1 /* permutation/test.c
   2  *
   3  * Copyright (C) 2000, 2007 Brian Gough
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 3 of the License, or (at
   8  * your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  */
  19
  20 #include <config.h>
  21 #include <stdlib.h>
  22 #include <stdio.h>
  23 #include <math.h>
  24 #include <gsl/gsl_permutation.h>
  25 #include <gsl/gsl_permute_double.h>
  26 #include <gsl/gsl_test.h>
  27 #include <gsl/gsl_ieee_utils.h>
  28
  29 unsigned int p5[120][5] = {
  30   {0, 1, 2, 3, 4}, {0, 1, 2, 4, 3}, {0, 1, 3, 2, 4}, {0, 1, 3, 4, 2},
  31   {0, 1, 4, 2, 3}, {0, 1, 4, 3, 2}, {0, 2, 1, 3, 4}, {0, 2, 1, 4, 3},
  32   {0, 2, 3, 1, 4}, {0, 2, 3, 4, 1}, {0, 2, 4, 1, 3}, {0, 2, 4, 3, 1},
  33   {0, 3, 1, 2, 4}, {0, 3, 1, 4, 2}, {0, 3, 2, 1, 4}, {0, 3, 2, 4, 1},
  34   {0, 3, 4, 1, 2}, {0, 3, 4, 2, 1}, {0, 4, 1, 2, 3}, {0, 4, 1, 3, 2},
  35   {0, 4, 2, 1, 3}, {0, 4, 2, 3, 1}, {0, 4, 3, 1, 2}, {0, 4, 3, 2, 1},
  36   {1, 0, 2, 3, 4}, {1, 0, 2, 4, 3}, {1, 0, 3, 2, 4}, {1, 0, 3, 4, 2},
  37   {1, 0, 4, 2, 3}, {1, 0, 4, 3, 2}, {1, 2, 0, 3, 4}, {1, 2, 0, 4, 3},
  38   {1, 2, 3, 0, 4}, {1, 2, 3, 4, 0}, {1, 2, 4, 0, 3}, {1, 2, 4, 3, 0},
  39   {1, 3, 0, 2, 4}, {1, 3, 0, 4, 2}, {1, 3, 2, 0, 4}, {1, 3, 2, 4, 0},
  40   {1, 3, 4, 0, 2}, {1, 3, 4, 2, 0}, {1, 4, 0, 2, 3}, {1, 4, 0, 3, 2},
  41   {1, 4, 2, 0, 3}, {1, 4, 2, 3, 0}, {1, 4, 3, 0, 2}, {1, 4, 3, 2, 0},
  42   {2, 0, 1, 3, 4}, {2, 0, 1, 4, 3}, {2, 0, 3, 1, 4}, {2, 0, 3, 4, 1},
  43   {2, 0, 4, 1, 3}, {2, 0, 4, 3, 1}, {2, 1, 0, 3, 4}, {2, 1, 0, 4, 3},
  44   {2, 1, 3, 0, 4}, {2, 1, 3, 4, 0}, {2, 1, 4, 0, 3}, {2, 1, 4, 3, 0},
  45   {2, 3, 0, 1, 4}, {2, 3, 0, 4, 1}, {2, 3, 1, 0, 4}, {2, 3, 1, 4, 0},
  46   {2, 3, 4, 0, 1}, {2, 3, 4, 1, 0}, {2, 4, 0, 1, 3}, {2, 4, 0, 3, 1},
  47   {2, 4, 1, 0, 3}, {2, 4, 1, 3, 0}, {2, 4, 3, 0, 1}, {2, 4, 3, 1, 0},
  48   {3, 0, 1, 2, 4}, {3, 0, 1, 4, 2}, {3, 0, 2, 1, 4}, {3, 0, 2, 4, 1},
  49   {3, 0, 4, 1, 2}, {3, 0, 4, 2, 1}, {3, 1, 0, 2, 4}, {3, 1, 0, 4, 2},
  50   {3, 1, 2, 0, 4}, {3, 1, 2, 4, 0}, {3, 1, 4, 0, 2}, {3, 1, 4, 2, 0},
  51   {3, 2, 0, 1, 4}, {3, 2, 0, 4, 1}, {3, 2, 1, 0, 4}, {3, 2, 1, 4, 0},
  52   {3, 2, 4, 0, 1}, {3, 2, 4, 1, 0}, {3, 4, 0, 1, 2}, {3, 4, 0, 2, 1},
  53   {3, 4, 1, 0, 2}, {3, 4, 1, 2, 0}, {3, 4, 2, 0, 1}, {3, 4, 2, 1, 0},
  54   {4, 0, 1, 2, 3}, {4, 0, 1, 3, 2}, {4, 0, 2, 1, 3}, {4, 0, 2, 3, 1},
  55   {4, 0, 3, 1, 2}, {4, 0, 3, 2, 1}, {4, 1, 0, 2, 3}, {4, 1, 0, 3, 2},
  56   {4, 1, 2, 0, 3}, {4, 1, 2, 3, 0}, {4, 1, 3, 0, 2}, {4, 1, 3, 2, 0},
  57   {4, 2, 0, 1, 3}, {4, 2, 0, 3, 1}, {4, 2, 1, 0, 3}, {4, 2, 1, 3, 0},
  58   {4, 2, 3, 0, 1}, {4, 2, 3, 1, 0}, {4, 3, 0, 1, 2}, {4, 3, 0, 2, 1},
  59   {4, 3, 1, 0, 2}, {4, 3, 1, 2, 0}, {4, 3, 2, 0, 1}, {4, 3, 2, 1, 0}
  60 } ;
  61
  62 unsigned int c5[120][5] = {
  63   {4, 3, 2, 1, 0}, {3, 4, 2, 1, 0}, {4, 2, 3, 1, 0}, {2, 3, 4, 1, 0},
  64   {2, 4, 3, 1, 0}, {3, 2, 4, 1, 0}, {4, 3, 1, 2, 0}, {3, 4, 1, 2, 0},
  65   {4, 1, 2, 3, 0}, {1, 2, 3, 4, 0}, {1, 2, 4, 3, 0}, {3, 1, 2, 4, 0},
  66   {4, 1, 3, 2, 0}, {1, 3, 4, 2, 0}, {4, 2, 1, 3, 0}, {2, 1, 3, 4, 0},
  67   {2, 4, 1, 3, 0}, {1, 3, 2, 4, 0}, {1, 4, 3, 2, 0}, {3, 1, 4, 2, 0},
  68   {2, 1, 4, 3, 0}, {3, 2, 1, 4, 0}, {1, 4, 2, 3, 0}, {2, 3, 1, 4, 0},
  69   {4, 3, 2, 0, 1}, {3, 4, 2, 0, 1}, {4, 2, 3, 0, 1}, {2, 3, 4, 0, 1},
  70   {2, 4, 3, 0, 1}, {3, 2, 4, 0, 1}, {4, 3, 0, 1, 2}, {3, 4, 0, 1, 2},
  71   {4, 0, 1, 2, 3}, {0, 1, 2, 3, 4}, {0, 1, 2, 4, 3}, {3, 0, 1, 2, 4},
  72   {4, 0, 1, 3, 2}, {0, 1, 3, 4, 2}, {4, 2, 0, 1, 3}, {2, 0, 1, 3, 4},
  73   {2, 4, 0, 1, 3}, {0, 1, 3, 2, 4}, {0, 1, 4, 3, 2}, {3, 0, 1, 4, 2},
  74   {2, 0, 1, 4, 3}, {3, 2, 0, 1, 4}, {0, 1, 4, 2, 3}, {2, 3, 0, 1, 4},
  75   {4, 3, 0, 2, 1}, {3, 4, 0, 2, 1}, {4, 0, 2, 3, 1}, {0, 2, 3, 4, 1},
  76   {0, 2, 4, 3, 1}, {3, 0, 2, 4, 1}, {4, 3, 1, 0, 2}, {3, 4, 1, 0, 2},
  77   {4, 1, 0, 2, 3}, {1, 0, 2, 3, 4}, {1, 0, 2, 4, 3}, {3, 1, 0, 2, 4},
  78   {4, 1, 3, 0, 2}, {1, 3, 4, 0, 2}, {4, 0, 2, 1, 3}, {0, 2, 1, 3, 4},
  79   {0, 2, 4, 1, 3}, {1, 3, 0, 2, 4}, {1, 4, 3, 0, 2}, {3, 1, 4, 0, 2},
  80   {0, 2, 1, 4, 3}, {3, 0, 2, 1, 4}, {1, 4, 0, 2, 3}, {0, 2, 3, 1, 4},
  81   {4, 0, 3, 2, 1}, {0, 3, 4, 2, 1}, {4, 2, 0, 3, 1}, {2, 0, 3, 4, 1},
  82   {2, 4, 0, 3, 1}, {0, 3, 2, 4, 1}, {4, 1, 0, 3, 2}, {1, 0, 3, 4, 2},
  83   {4, 2, 1, 0, 3}, {2, 1, 0, 3, 4}, {2, 4, 1, 0, 3}, {1, 0, 3, 2, 4},
  84   {4, 0, 3, 1, 2}, {0, 3, 4, 1, 2}, {4, 1, 2, 0, 3}, {1, 2, 0, 3, 4},
  85   {1, 2, 4, 0, 3}, {0, 3, 1, 2, 4}, {0, 3, 1, 4, 2}, {1, 4, 0, 3, 2},
  86   {1, 4, 2, 0, 3}, {0, 3, 2, 1, 4}, {2, 1, 4, 0, 3}, {2, 0, 3, 1, 4},
  87   {0, 4, 3, 2, 1}, {3, 0, 4, 2, 1}, {2, 0, 4, 3, 1}, {3, 2, 0, 4, 1},
  88   {0, 4, 2, 3, 1}, {2, 3, 0, 4, 1}, {1, 0, 4, 3, 2}, {3, 1, 0, 4, 2},
  89   {2, 1, 0, 4, 3}, {3, 2, 1, 0, 4}, {1, 0, 4, 2, 3}, {2, 3, 1, 0, 4},
  90   {0, 4, 3, 1, 2}, {3, 0, 4, 1, 2}, {1, 2, 0, 4, 3}, {3, 1, 2, 0, 4},
  91   {0, 4, 1, 2, 3}, {1, 2, 3, 0, 4}, {1, 3, 0, 4, 2}, {0, 4, 1, 3, 2},
  92   {0, 4, 2, 1, 3}, {1, 3, 2, 0, 4}, {2, 0, 4, 1, 3}, {2, 1, 3, 0, 4}
  93 } ;
  94
  95 unsigned int cycles[120] = {
  96   5, 4, 4, 3, 3, 4, 4, 3, 3, 2,
  97   2, 3, 3, 2, 4, 3, 3, 2, 2, 3,
  98   3, 4, 2, 3, 4, 3, 3, 2, 2, 3,
  99   3, 2, 2, 1, 1, 2, 2, 1, 3, 2,
 100   2, 1, 1, 2, 2, 3, 1, 2, 3, 2,
 101   2, 1, 1, 2, 4, 3, 3, 2, 2, 3,
 102   3, 2, 2, 1, 1, 2, 2, 3, 1, 2,
 103   2, 1, 2, 1, 3, 2, 2, 1, 3, 2,
 104   4, 3, 3, 2, 2, 1, 3, 2, 2, 1,
 105   1, 2, 2, 1, 3, 2, 1, 2, 2, 3,
 106   1, 2, 2, 3, 3, 4, 2, 3, 1, 2,
 107   2, 3, 1, 2, 2, 1, 1, 2, 2, 3
 108 } ;
 109
 110 unsigned int inversions[120] = {
 111   0, 1, 1, 2, 2, 3, 1, 2, 2, 3,
 112   3, 4, 2, 3, 3, 4, 4, 5, 3, 4,
 113   4, 5, 5, 6, 1, 2, 2, 3, 3, 4,
 114   2, 3, 3, 4, 4, 5, 3, 4, 4, 5,
 115   5, 6, 4, 5, 5, 6, 6, 7, 2, 3,
 116   3, 4, 4, 5, 3, 4, 4, 5, 5, 6,
 117   4, 5, 5, 6, 6, 7, 5, 6, 6, 7,
 118   7, 8, 3, 4, 4, 5, 5, 6, 4, 5,
 119   5, 6, 6, 7, 5, 6, 6, 7, 7, 8,
 120   6, 7, 7, 8, 8, 9, 4, 5, 5, 6,
 121   6, 7, 5, 6, 6, 7, 7, 8, 6, 7,
 122   7, 8, 8, 9, 7, 8, 8, 9, 9, 10
 123 } ;
 124
 125 int
 126 main (void)
 127 {
 128   gsl_ieee_env_setup ();
 129
 130   {
 131     int i = 0, j, status = 0;
 132
 133     gsl_permutation * p ;
 134
 135     p = gsl_permutation_alloc (5);
 136
 137     gsl_permutation_init (p);
 138
 139     do
 140       {
 141         for (j = 0; j < 5; j++)
 142           {
 143             status |= (p->data[j] != p5[i][j]);
 144           }
 145
 146         i++;
 147       }
 148     while (gsl_permutation_next(p) == GSL_SUCCESS);
 149
 150     gsl_test(status, "gsl_permutation_next, 5-th order permutation, 120 steps");
 151
 152     do
 153       {
 154         i--;
 155
 156         for (j = 0; j < 5; j++)
 157           {
 158             status |= (p->data[j] != p5[i][j]);
 159           }
 160       }
 161     while (gsl_permutation_prev(p) == GSL_SUCCESS);
 162
 163     gsl_test(status, "gsl_permutation_prev, 5-th order permutation, 120 steps");
 164
 165     gsl_permutation_free (p);
 166   }
 167
 168 #ifdef JUNK
 169   {
 170     int i;
 171     int status = 0 ;
 172
 173     gsl_permutation * p1 = gsl_permutation_alloc (5);
 174     gsl_permutation * p2 = gsl_permutation_alloc (5);
 175     gsl_permutation * p = gsl_permutation_alloc (5);
 176
 177     double v[5] = { 100.0, 101.0, 102.0, 103.0, 104.0 } ;
 178
 179     gsl_permutation_init (p1);
 180
 181     do
 182       {
 183         gsl_permutation_init (p2);
 184
 185         do
 186           {
 187             double x[5], y[5];
 188
 189             /* Compute x= p1 p2 v */
 190             memcpy (x, v, 5 * sizeof(double));
 191             gsl_permute (p2->data, x, 1, 5);
 192             gsl_permute (p1->data, x, 1, 5);
 193
 194             /* Compute P= p1 p2, y = P v */
 195             gsl_permutation_mul (p, p1, p2);
 196             memcpy (y, v, 5 * sizeof(double));
 197             gsl_permute (p->data, y, 1, 5);
 198
 199             for (i = 0; i < 5; i++)
 200               {
 201                 if (x[i] != y[i])
 202                   status = 1;
 203               }
 204
 205             if (status == 1)
 206               break;
 207           }
 208         while (gsl_permutation_next(p2) == GSL_SUCCESS);
 209
 210         if (status == 1)
 211           break;
 212       }
 213     while (gsl_permutation_next(p1) == GSL_SUCCESS);
 214
 215     gsl_permutation_free (p1);
 216     gsl_permutation_free (p2);
 217     gsl_permutation_free (p);
 218
 219     gsl_test(status, "gsl_permutation_mul, all 5-th order combinations");
 220   }
 221 #endif
 222
 223   /* testing cycles representations */
 224   {
 225     int i = 0, j, status = 0;
 226
 227     gsl_permutation * p = gsl_permutation_alloc (5);
 228
 229     gsl_permutation * plin = gsl_permutation_alloc (5);
 230     gsl_permutation * pcan = gsl_permutation_alloc (5);
 231
 232     gsl_permutation_init (p);
 233
 234     do
 235       {
 236         gsl_permutation_memcpy (plin, p);
 237
 238         for (j = 0; j < 5; j++)
 239           {
 240             pcan->data[j] = 0;
 241           }
 242
 243         gsl_permutation_linear_to_canonical (pcan, plin);
 244
 245         for (j = 0; j < 5; j++)
 246           {
 247             status |= (pcan->data[j] != c5[i][j]);
 248           }
 249
 250         status |= (gsl_permutation_canonical_cycles (pcan) != cycles[i]);
 251
 252         status |= (gsl_permutation_linear_cycles (plin) != cycles[i]);
 253
 254         for (j = 0; j < 5; j++)
 255           {
 256             plin->data[j] = 0;
 257           }
 258
 259         gsl_permutation_canonical_to_linear (plin, pcan);
 260
 261         for (j = 0; j < 5; j++)
 262           {
 263             status |= (plin->data[j] != p5[i][j]);
 264           }
 265
 266         i++;
 267       }
 268     while (gsl_permutation_next(p) == GSL_SUCCESS);
 269
 270     gsl_permutation_free (p);
 271     gsl_permutation_free (plin);
 272     gsl_permutation_free (pcan);
 273
 274     gsl_test (status, "gsl_permutation canonical conversion, 5-th order permutation, 120 steps");
 275   }
 276
 277   /* testing number of inversions */
 278   {
 279     int i = 0, status = 0;
 280
 281     gsl_permutation * p = gsl_permutation_alloc (5);
 282
 283     gsl_permutation_init (p);
 284
 285     do
 286       {
 287         status |= gsl_permutation_inversions (p) != inversions[i];
 288         i++;
 289       }
 290     while (gsl_permutation_next(p) == GSL_SUCCESS);
 291
 292     gsl_permutation_free (p);
 293
 294     gsl_test (status, "gsl_permutation_inversions, 5-th order permutation, 120 steps");
 295   }
 296
 297
 298   exit (gsl_test_summary());
 299 }
 300