GNU Astronomy Utilities

Next: , Previous: , Up: Gnuastro library   [Contents][Index]

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 future244 we will submit these implementations to GSL. If they are finally incorporated there, we will delete this section in future versions.

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.

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.

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.



Gnuastro’s Task 14497. If this task is still “postponed” when you are reading this and you are interested to help, your contributions would be very welcome. Both Gnuastro and GSL developers are very busy, hence both would appreciate your help.

Next: Matching (match.h), Previous: K-d tree (kdtree.h), Up: Gnuastro library   [Contents][Index]