## File: Permutation-Examples.html

package info (click to toggle)
gsl-ref-html 2.3-1
• area: non-free
• in suites: buster
• size: 6,876 kB
• ctags: 4,574
• sloc: makefile: 35
 file content (184 lines) | stat: -rw-r--r-- 6,816 bytes parent folder | download
 `123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184` `````` GNU Scientific Library – Reference Manual: Permutation Examples

9.9 Examples

The example program below creates a random permutation (by shuffling the elements of the identity) and finds its inverse.

#include <stdio.h> #include <gsl/gsl_rng.h> #include <gsl/gsl_randist.h> #include <gsl/gsl_permutation.h>  int main (void)  {   const size_t N = 10;   const gsl_rng_type * T;   gsl_rng * r;    gsl_permutation * p = gsl_permutation_alloc (N);   gsl_permutation * q = gsl_permutation_alloc (N);    gsl_rng_env_setup();   T = gsl_rng_default;   r = gsl_rng_alloc (T);    printf ("initial permutation:");     gsl_permutation_init (p);   gsl_permutation_fprintf (stdout, p, " %u");   printf ("\n");    printf (" random permutation:");     gsl_ran_shuffle (r, p->data, N, sizeof(size_t));   gsl_permutation_fprintf (stdout, p, " %u");   printf ("\n");    printf ("inverse permutation:");     gsl_permutation_inverse (q, p);   gsl_permutation_fprintf (stdout, q, " %u");   printf ("\n");    gsl_permutation_free (p);   gsl_permutation_free (q);   gsl_rng_free (r);    return 0; }

Here is the output from the program,

\$ ./a.out  initial permutation: 0 1 2 3 4 5 6 7 8 9  random permutation: 1 3 5 2 7 6 0 4 9 8 inverse permutation: 6 0 3 1 7 2 5 4 9 8

The random permutation p[i] and its inverse q[i] are related through the identity p[q[i]] = i, which can be verified from the output.

The next example program steps forwards through all possible third order permutations, starting from the identity,

#include <stdio.h> #include <gsl/gsl_permutation.h>  int main (void)  {   gsl_permutation * p = gsl_permutation_alloc (3);    gsl_permutation_init (p);    do     {       gsl_permutation_fprintf (stdout, p, " %u");       printf ("\n");    }   while (gsl_permutation_next(p) == GSL_SUCCESS);    gsl_permutation_free (p);    return 0; }

Here is the output from the program,

\$ ./a.out   0 1 2  0 2 1  1 0 2  1 2 0  2 0 1  2 1 0

The permutations are generated in lexicographic order. To reverse the sequence, begin with the final permutation (which is the reverse of the identity) and replace gsl_permutation_next with gsl_permutation_prev.

``````