12.3.20 Permutations (permutation.h) ¶

Permutation is the technical name for re-ordering of values. The need for permutations occurs a lot during (mainly low-level) processing. To do permutation, you must provide two inputs: an array of values (that you want to re-order in place) and a permutation array which contains the new index of each element (let’s call it perm). The diagram below shows the input array before and after the re-ordering.

permute:    AFTER[ i       ] = BEFORE[ perm[i] ]     i = 0 .. N-1
inverse:    AFTER[ perm[i] ] = BEFORE[ i       ]     i = 0 .. N-1

The functions here are a re-implementation of the GNU Scientific Library’s gsl_permute function. The reason we did not use that function was that it uses system-specific types (like long and int) which can have different widths on different systems, hence are not easily convertible to Gnuastro’s fixed width types (see Numeric data types). There is also a separate function for each type, heavily using macros to allow a base function to work on all the types. Thus it is hard to read/understand. Hence, Gnuastro contains a re-write of their steps in a new type-agnostic method which is a single function that can work on any type.

As described in GSL’s source code and manual, this implementation comes from Donald Knuth’s Art of computer programming book, in the "Sorting and Searching" chapter of Volume 3 (3rd ed). Exercise 10 of Section 5.2 defines the problem and in the answers, Knuth describes the solution. So if you are interested, please have a look there for more.

We are in contact with the GSL developers and in the future²⁷¹ we will submit these implementations to GSL. If they are finally incorporated there, we will delete this section in future versions.

Function:
void
gal_permutation_check (size_t *permutation, size_t size) ¶

Print how permutation will re-order an array that has size elements for each element in one one line.

Function:
void
gal_permutation_apply (gal_data_t *input, size_t *permutation) ¶

Apply permutation on the input dataset (can have any type), see above for the definition of permutation.

Function:
void
gal_permutation_apply_inverse (gal_data_t *input, size_t *permutation) ¶

Apply the inverse of permutation on the input dataset (can have any type), see above for the definition of permutation.

Function:
void
gal_permutation_transpose_2d (gal_data_t *input) ¶

Transpose an input 2D matrix into a new dataset. If the input is not a square, this function will change the input->array element to a newly allocated array (the old one will be freed internally). Therefore, in case you have already stored input->array for other usage before this function, and the input is not a square, be sure to update the previously stored pointer if the input is not a square.