gdsl  1.6
Permutation manipulation module

Typedefs

typedef struct gdsl_perm * gdsl_perm_t
 GDSL permutation type.
typedef void(* gdsl_perm_write_func_t )(ulong E, FILE *OUTPUT_FILE, gdsl_location_t POSITION, void *USER_DATA)
 GDSL permutation write function type.
typedef struct gdsl_perm_data * gdsl_perm_data_t

Enumerations

enum  gdsl_perm_position_t { GDSL_PERM_POSITION_FIRST = 1, GDSL_PERM_POSITION_LAST = 2 }
 This type is for gdsl_perm_write_func_t. More...

Functions

gdsl_perm_t gdsl_perm_alloc (const char *NAME, const ulong N)
 Create a new permutation.
void gdsl_perm_free (gdsl_perm_t P)
 Destroy a permutation.
gdsl_perm_t gdsl_perm_copy (const gdsl_perm_t P)
 Copy a permutation.
const char * gdsl_perm_get_name (const gdsl_perm_t P)
 Get the name of a permutation.
ulong gdsl_perm_get_size (const gdsl_perm_t P)
 Get the size of a permutation.
ulong gdsl_perm_get_element (const gdsl_perm_t P, const ulong INDIX)
 Get the (INDIX+1)-th element from a permutation.
ulonggdsl_perm_get_elements_array (const gdsl_perm_t P)
 Get the array elements of a permutation.
ulong gdsl_perm_linear_inversions_count (const gdsl_perm_t P)
 Count the inversions number into a linear permutation.
ulong gdsl_perm_linear_cycles_count (const gdsl_perm_t P)
 Count the cycles number into a linear permutation.
ulong gdsl_perm_canonical_cycles_count (const gdsl_perm_t P)
 Count the cycles number into a canonical permutation.
gdsl_perm_t gdsl_perm_set_name (gdsl_perm_t P, const char *NEW_NAME)
 Set the name of a permutation.
gdsl_perm_t gdsl_perm_linear_next (gdsl_perm_t P)
 Get the next permutation from a linear permutation.
gdsl_perm_t gdsl_perm_linear_prev (gdsl_perm_t P)
 Get the previous permutation from a linear permutation.
gdsl_perm_t gdsl_perm_set_elements_array (gdsl_perm_t P, const ulong *ARRAY)
 Initialize a permutation with an array of values.
gdsl_perm_t gdsl_perm_multiply (gdsl_perm_t RESULT, const gdsl_perm_t ALPHA, const gdsl_perm_t BETA)
 Multiply two permutations.
gdsl_perm_t gdsl_perm_linear_to_canonical (gdsl_perm_t Q, const gdsl_perm_t P)
 Convert a linear permutation to its canonical form.
gdsl_perm_t gdsl_perm_canonical_to_linear (gdsl_perm_t Q, const gdsl_perm_t P)
 Convert a canonical permutation to its linear form.
gdsl_perm_t gdsl_perm_inverse (gdsl_perm_t P)
 Inverse in place a permutation.
gdsl_perm_t gdsl_perm_reverse (gdsl_perm_t P)
 Reverse in place a permutation.
gdsl_perm_t gdsl_perm_randomize (gdsl_perm_t P)
 Randomize a permutation.
gdsl_element_tgdsl_perm_apply_on_array (gdsl_element_t *V, const gdsl_perm_t P)
 Apply a permutation on to a vector.
void gdsl_perm_write (const gdsl_perm_t P, const gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the elements of a permutation to a file.
void gdsl_perm_write_xml (const gdsl_perm_t P, const gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the elements of a permutation to a file into XML.
void gdsl_perm_dump (const gdsl_perm_t P, const gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of a permutation to a file.

Typedef Documentation

typedef struct gdsl_perm* gdsl_perm_t

GDSL permutation type.

This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module.

Definition at line 50 of file gdsl_perm.h.

typedef void(* gdsl_perm_write_func_t)(ulong E, FILE *OUTPUT_FILE, gdsl_location_t POSITION, void *USER_DATA)

GDSL permutation write function type.

Parameters:
EThe permutation element to write
OUTPUT_FILEThe file where to write E
POSITIONis an or-ed combination of gdsl_perm_position_t values to indicate where E is located into the gdsl_perm_t mapped.
USER_DATAUser's datas

Definition at line 74 of file gdsl_perm.h.

typedef struct gdsl_perm_data* gdsl_perm_data_t

Definition at line 80 of file gdsl_perm.h.


Enumeration Type Documentation

This type is for gdsl_perm_write_func_t.

Enumerator:
GDSL_PERM_POSITION_FIRST 

When element is at first position

GDSL_PERM_POSITION_LAST 

When element is at last position

Definition at line 55 of file gdsl_perm.h.


Function Documentation

gdsl_perm_t gdsl_perm_alloc ( const char *  NAME,
const ulong  N 
)

Create a new permutation.

Allocate a new permutation data structure of size N wich name is set to a copy of NAME.

Note:
Complexity: O( N )
Precondition:
N > 0
Parameters:
NThe number of elements of the permutation to create.
NAMEThe name of the new permutation to create
Returns:
the newly allocated identity permutation in its linear form in case of success.
NULL in case of insufficient memory.
See also:
gdsl_perm_free()
gdsl_perm_copy()

Destroy a permutation.

Deallocate the permutation P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
PThe permutation to destroy
See also:
gdsl_perm_alloc()
gdsl_perm_copy()

Copy a permutation.

Create and return a copy of the permutation P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t.
Postcondition:
The returned permutation must be deallocated with gdsl_perm_free.
Parameters:
PThe permutation to copy.
Returns:
a copy of P in case of success.
NULL in case of insufficient memory.
See also:
gdsl_perm_alloc
gdsl_perm_free
const char* gdsl_perm_get_name ( const gdsl_perm_t  P)

Get the name of a permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid gdsl_perm_t
Postcondition:
The returned string MUST NOT be freed.
Parameters:
PThe permutation to get the name from
Returns:
the name of the permutation P.
See also:
gdsl_perm_set_name()

Get the size of a permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
PThe permutation to get the size from.
Returns:
the number of elements of P (noted |P|).
See also:
gdsl_perm_get_element()
gdsl_perm_get_elements_array()
ulong gdsl_perm_get_element ( const gdsl_perm_t  P,
const ulong  INDIX 
)

Get the (INDIX+1)-th element from a permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid gdsl_perm_t & <= 0 INDIX < |P|
Parameters:
PThe permutation to use.
INDIXThe indix of the value to get.
Returns:
the value at the INDIX-th position in the permutation P.
See also:
gdsl_perm_get_size()
gdsl_perm_get_elements_array()

Get the array elements of a permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
PThe permutation to get datas from.
Returns:
the values array of the permutation P.
See also:
gdsl_perm_get_element()
gdsl_perm_set_elements_array()

Count the inversions number into a linear permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear gdsl_perm_t
Parameters:
PThe linear permutation to use.
Returns:
the number of inversions into the linear permutation P.

Count the cycles number into a linear permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear gdsl_perm_t
Parameters:
PThe linear permutation to use.
Returns:
the number of cycles into the linear permutation P.
See also:
gdsl_perm_canonical_cycles_count()

Count the cycles number into a canonical permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid canonical gdsl_perm_t
Parameters:
PThe canonical permutation to use.
Returns:
the number of cycles into the canonical permutation P.
See also:
gdsl_perm_linear_cycles_count()
gdsl_perm_t gdsl_perm_set_name ( gdsl_perm_t  P,
const char *  NEW_NAME 
)

Set the name of a permutation.

Change the previous name of the permutation P to a copy of NEW_NAME.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
PThe permutation to change the name
NEW_NAMEThe new name of P
Returns:
the modified permutation in case of success.
NULL in case of insufficient memory.
See also:
gdsl_perm_get_name()

Get the next permutation from a linear permutation.

The permutation P is modified to become the next permutation after P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear gdsl_perm_t & |P| > 1
Parameters:
PThe linear permutation to modify
Returns:
the next permutation after the permutation P.
NULL if P is already the last permutation.
See also:
gdsl_perm_linear_prev()

Get the previous permutation from a linear permutation.

The permutation P is modified to become the previous permutation before P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear gdsl_perm_t & |P| >= 2
Parameters:
PThe linear permutation to modify
Returns:
the previous permutation before the permutation P.
NULL if P is already the first permutation.
See also:
gdsl_perm_linear_next()

Initialize a permutation with an array of values.

Initialize the permutation P with the values contained in the array of values ARRAY. If ARRAY does not design a permutation, then P is left unchanged.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t & V != NULL & |V| == |P|
Parameters:
PThe permutation to initialize
ARRAYThe array of values to initialize P
Returns:
the modified permutation in case of success.
NULL in case V does not design a valid permutation.
See also:
gdsl_perm_get_elements_array()
gdsl_perm_t gdsl_perm_multiply ( gdsl_perm_t  RESULT,
const gdsl_perm_t  ALPHA,
const gdsl_perm_t  BETA 
)

Multiply two permutations.

Compute the product of the permutations ALPHA x BETA and puts the result in RESULT without modifying ALPHA and BETA.

Note:
Complexity: O( |RESULT| )
Precondition:
RESULT, ALPHA and BETA must be valids gdsl_perm_t & |RESULT| == |ALPHA| == |BETA|
Parameters:
RESULTThe result of the product ALPHA x BETA
ALPHAThe first permutation used in the product
BETAThe second permutation used in the product
Returns:
RESULT, the result of the multiplication ALPHA x BETA.

Convert a linear permutation to its canonical form.

Convert the linear permutation P to its canonical form. The resulted canonical permutation is placed into Q without modifying P.

Note:
Complexity: O( |P| )
Precondition:
P & Q must be valids gdsl_perm_t & |P| == |Q| & P != Q
Parameters:
QThe canonical form of P
PThe linear permutation used to compute its canonical form into Q
Returns:
the canonical form Q of the permutation P.
See also:
gdsl_perm_canonical_to_linear()

Convert a canonical permutation to its linear form.

Convert the canonical permutation P to its linear form. The resulted linear permutation is placed into Q without modifying P.

Note:
Complexity: O( |P| )
Precondition:
P & Q must be valids gdsl_perm_t & |P| == |Q| & P != Q
Parameters:
QThe linear form of P
PThe canonical permutation used to compute its linear form into Q
Returns:
the linear form Q of the permutation P.
See also:
gdsl_perm_linear_to_canonical()

Inverse in place a permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
PThe permutation to invert
Returns:
the inverse permutation of P in case of success.
NULL in case of insufficient memory.
See also:
gdsl_perm_reverse()

Reverse in place a permutation.

Note:
Complexity: O( |P| / 2 )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
PThe permutation to reverse
Returns:
the mirror image of the permutation P
See also:
gdsl_perm_inverse()

Randomize a permutation.

The permutation P is randomized in an efficient way, using inversions array.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
PThe permutation to randomize
Returns:
the mirror image ~P of the permutation of P in case of success.
NULL in case of insufficient memory.

Apply a permutation on to a vector.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t & |P| == |V|
Parameters:
VThe vector/array to reorder according to P
PThe permutation to use to reorder V
Returns:
the reordered array V according to the permutation P in case of success.
NULL in case of insufficient memory.
void gdsl_perm_write ( const gdsl_perm_t  P,
const gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write the elements of a permutation to a file.

Write the elements of the permuation P to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t & WRITE_F != NULL & OUTPUT_FILE != NULL
Parameters:
PThe permutation to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write P's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_perm_write_xml()
gdsl_perm_dump()
void gdsl_perm_write_xml ( const gdsl_perm_t  P,
const gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write the elements of a permutation to a file into XML.

Write the elements of the permutation P to OUTPUT_FILE, into XML language. If WRITE_F != NULL, then uses WRITE_F function to write P's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t & OUTPUT_FILE != NULL
Parameters:
PThe permutation to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write P's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_perm_write()
gdsl_perm_dump()
void gdsl_perm_dump ( const gdsl_perm_t  P,
const gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Dump the internal structure of a permutation to a file.

Dump the structure of the permutation P to OUTPUT_FILE. If WRITE_F != NULL, then uses WRITE_F function to write P's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t & OUTPUT_FILE != NULL
Parameters:
PThe permutation to dump.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write P's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_perm_write()
gdsl_perm_write_xml()