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
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
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 future137 we will submit these implementations to GSL. If they are finally incorporated there, we will delete this section in future versions.
permutation will re-order an array that has
elements for each element in one one line.
permutation on the
input dataset (can have any type),
see above for the definition of 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.