Main Page | Modules | File List | Globals

Permutation manipulation module


Typedefs

typedef gdsl_perm * gdsl_perm_t
 GDSL permutation type.

typedef void(* gdsl_perm_write_func_t )(ulong E, FILE *OUTPUT_FILE, gdsl_perm_position_t POSITION, void *USER_DATA)
 GDSL permutation write function type.


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_perm_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 49 of file gdsl_perm.h.

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

GDSL permutation write function type.

Parameters:
E The permutation element to write
OUTPUT_FILE The file where to write E
POSITION is an or-ed combination of gdsl_perm_position_t values to indicate where E is located into the gdsl_perm_t mapped.
USER_DATA User's datas

Definition at line 73 of file gdsl_perm.h.


Enumeration Type Documentation

enum gdsl_perm_position_t
 

This type is for gdsl_perm_write_func_t.

Enumeration values:
GDSL_PERM_POSITION_FIRST  When element is at first position
GDSL_PERM_POSITION_LAST  When element is at last position

Definition at line 54 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:
N The number of elements of the permutation to create.
NAME The 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()

gdsl_element_t* gdsl_perm_apply_on_array gdsl_element_t V,
const gdsl_perm_t  P
 

Apply a permutation on to a vector.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t & |P| == |V|
Parameters:
V The vector/array to reorder according to P
P The 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.

ulong gdsl_perm_canonical_cycles_count const gdsl_perm_t  P  ) 
 

Count the cycles number into a canonical permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid canonical gdsl_perm_t
Parameters:
P The 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_canonical_to_linear gdsl_perm_t  Q,
const gdsl_perm_t  P
 

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:
Q The linear form of P
P The 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()

gdsl_perm_t gdsl_perm_copy const gdsl_perm_t  P  ) 
 

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:
P The 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

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:
P The permutation to dump.
WRITE_F The write function.
OUTPUT_FILE The file where to write P's elements.
USER_DATA User's datas passed to WRITE_F.
See also:
gdsl_perm_write()

gdsl_perm_write_xml()

void gdsl_perm_free gdsl_perm_t  P  ) 
 

Destroy a permutation.

Deallocate the permutation P.

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

gdsl_perm_copy()

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:
P The permutation to use.
INDIX The 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()

ulong* gdsl_perm_get_elements_array const gdsl_perm_t  P  ) 
 

Get the array elements of a permutation.

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

gdsl_perm_set_elements_array()

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:
P The permutation to get the name from
Returns:
the name of the permutation P.
See also:
gdsl_perm_set_name()

ulong gdsl_perm_get_size const gdsl_perm_t  P  ) 
 

Get the size of a permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
P The 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()

gdsl_perm_t gdsl_perm_inverse gdsl_perm_t  P  ) 
 

Inverse in place a permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid gdsl_perm_t
Parameters:
P The permutation to invert
Returns:
the inverse permutation of P in case of success.

NULL in case of insufficient memory.

See also:
gdsl_perm_reverse()

ulong gdsl_perm_linear_cycles_count const gdsl_perm_t  P  ) 
 

Count the cycles number into a linear permutation.

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

ulong gdsl_perm_linear_inversions_count const gdsl_perm_t  P  ) 
 

Count the inversions number into a linear permutation.

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

gdsl_perm_t gdsl_perm_linear_next gdsl_perm_t  P  ) 
 

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:
P The 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()

gdsl_perm_t gdsl_perm_linear_prev gdsl_perm_t  P  ) 
 

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:
P The 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()

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.

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:
Q The canonical form of P
P The 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()

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:
RESULT The result of the product ALPHA x BETA
ALPHA The first permutation used in the product
BETA The second permutation used in the product
Returns:
RESULT, the result of the multiplication of the permutations A and B.

gdsl_perm_t gdsl_perm_randomize gdsl_perm_t  P  ) 
 

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:
P The permutation to randomize
Returns:
the mirror image ~P of the permutation of P in case of success.

NULL in case of insufficient memory.

gdsl_perm_t gdsl_perm_reverse gdsl_perm_t  P  ) 
 

Reverse in place a permutation.

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

gdsl_perm_t gdsl_perm_set_elements_array gdsl_perm_t  P,
const ulong ARRAY
 

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:
P The permutation to initialize
ARRAY The 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_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:
P The permutation to change the name
NEW_NAME The new name of P
Returns:
the modified permutation in case of success.

NULL in case of insufficient memory.

See also:
gdsl_perm_get_name()

void gdsl_perm_write const gdsl_perm_t  P,
const gdsl_perm_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:
P The permutation to write.
WRITE_F The write function.
OUTPUT_FILE The file where to write P's elements.
USER_DATA User'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:
P The permutation to write.
WRITE_F The write function.
OUTPUT_FILE The file where to write P's elements.
USER_DATA User's datas passed to WRITE_F.
See also:
gdsl_perm_write()

gdsl_perm_dump()


Generated on Fri Oct 1 18:54:53 2004 for GDSL by doxygen 1.3.5