Next: Matching, Previous: K-d tree, Up: Gnuastro library [Contents][Index]

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 didn’t 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^{186}
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.

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

Next: Matching, Previous: K-d tree, Up: Gnuastro library [Contents][Index]

GNU Astronomy Utilities 0.13 manual, September 2020.