Common Lisp Package: CL-PERMUTATION

README:

FUNCTION

Public

CYCLES-TO-ONE-LINE (CYCLES)

Convert CYCLES to one-line notation. This is not the same as FROM-CYCLES.

ENABLE-PERM-READER

Enable the use of #[...] for perms.

FROM-CYCLES (CYCLES &OPTIONAL (SIZE 0))

Convert a cycle representation of a permutation CYCLES to the standard representation.

GENERATE-PERM-GROUP (GENERATORS)

Generate a permutation group generated by the list of permutations GENERATORS.

GROUP-ELEMENT-P (PERM GROUP)

Decide if the permutation PERM is an element of the group GROUP.

GROUP-FROM (GENERATORS-AS-LISTS)

Generate a permutation group from a list of generators, which are represented as lists.

GROUP-FROM-CYCLES (GENERATORS-AS-CYCLES SIZE)

Generate a permutation group from a list of generators, which are represented as cycles.

GROUP-ORDER (GROUP)

Compute the order of the permutation group GROUP.

LIST-TO-PERM (LIST)

Construct a perm from a list LIST.

MAKE-PERM (&REST ELEMENTS)

Construct a permutation from the numbers ELEMENTS.

MAKE-PERM-GENERATOR (N)

Create a generator that generates permutations of size N.

NORMALIZE-CYCLE-ORDER (CYCLE)

Rotate a cycle CYCLE so its least value is syntactically first.

NORMALIZE-CYCLES (CYCLES)

Normalize each cycle in CYCLES, then normalize the list of cycles in descending length (or if the length is the same, ascending first element).

ORBIT-OF (N PERM)

Compute the orbit of the element N in the permutation PERM.

PERM-COMPOSE (P1 P2)

Compose the permutations P1 and P2: x |-> P2(P1(x)).

PERM-EVAL (PERM N)

Evaluate the permutation PERM at index N.

PERM-EVAL* (PERM N)

Evaluate the permutation PERM at index N. If N is larger than the size of the permutation, return the fixed point.

PERM-EVEN-P (PERM)

Is PERM an even permutation?

PERM-EXPT (PERM N)

Raise a permutation PERM to the Nth power.

PERM-FIXPOINTS (PERM &OPTIONAL (N (PERM-SIZE PERM)))

Return a list of the fixed points in PERM less than or equal to N, which is the perm's size by default.

PERM-IDENTITY (N)

The identity permutation of size N.

PERM-IDENTITY-P (PERM)

Is the permutation PERM an identity permutation?

PERM-INVERSE (PERM)

Find the inverse of the permutation PERM.

PERM-INVERSE-EVAL (PERM N)

Evaluate the inverse of the permutation PERM at index N.

PERM-INVERSE-EVAL* (PERM N)

Evaluate the inverse of the permutation PERM at index N. If N is larger than the size of the permutation, return the fixed point.

PERM-LENGTH (PERM)

Count the number of inversions in the permutation PERM.

PERM-ODD-P (PERM)

Is PERM an odd permutation?

PERM-ORDER (PERM)

Compute the order of a permutation PERM.

PERM-REF (PERM N)

Compute the zero-based index of PERM at N.

PERM-SIGN (PERM)

The sign of a permutation PERM.

PERM-SIZE (PERM)

The size of a permutation PERM.

PERM-TO-LIST (PERM)

Convert a permutation PERM to a list representation.

PERM-TO-WORD (PERM)

Convert a permutation PERM to a word, represented by an array.

PERM-TRANSPOSE-ENTRIES (PERM A B)

Transpose the entries A and B in PERM.

PERM-TRANSPOSE-INDEXES (PERM A B)

Transpose the indexes A and B in PERM.

PERMUTE (PERM A &KEY TYPE)

Permute the sequence A according to PERM. The return an array by default unless TYPE is specified.

RANDOM-GROUP-ELEMENT (GROUP)

Generate a random element of the group GROUP.

RANDOM-PERM (N &OPTIONAL (PARITY ANY))

Make a random permutation of size N. PARITY specifies the parity of the permutation: * :ANY for any permutation * :EVEN for only even permutations * :ODD for only odd permutations

ROTATE-CYCLE-CLOCKWISE (CYCLE &OPTIONAL (N 1))

Rotate the elements of a cycle syntactically clockwise, a total of N times. When N is negative, rotate counterclockwise.

ROTATE-CYCLE-COUNTERCLOCKWISE (CYCLE &OPTIONAL (N 1))

Rotate the elements of a cycle CYCLE syntactically counterclockwise, a total of N times. When N is negative, rotate clockwise.

TO-CYCLES (PERM &KEY (NORMALIZEP T))

Convert a permutation PERM in its standard representation to its cycle representation.

TRANSVERSAL-DECOMPOSITION (PERM GROUP &KEY REMOVE-IDENTITIES)

Decompose the permutation PERM into transversal sigmas of the group GROUP.

WORD-TO-PERM (WORD)

Convert a word WORD (an array) to a permutation.

Private

ALLOCATE-PERM-VECTOR (N)

Allocate a vector compatible with a size-N permutation.

ASSERT-VALID-PERMUTATION-ELEMENTS (ELEMENTS)

Verify (via assertions) that the elements

CONTAINS-1-TO-N (ELEMENTS)

Check that ELEMENTS contains the integers between 1 and the length of the list, inclusive.

DECOMPOSE-CYCLE-TO-MAPS (CYCLE)

Convert a cycle CYCLE to a list of pairs (a_i . b_i) such that a permutation is the composition of a_i |-> b_i.

HASH-TABLE-KEY-EXISTS-P (HASH-TABLE KEY)

Check of KEY exists in HASH-TABLE.

HASH-TABLE-KEYS (HASH-TABLE)

Return a list of the hash table keys of HASH-TABLE.

HASH-TABLE-VALUES (HASH-TABLE)

Return a list of the hash table values of HASH-TABLE.

INDEX-TO-HASH-TABLE-KEY (HASH-TABLE N)

Get the Nth key from HASH-TABLE. Ordering is not specified. This function just guarantees we can map N to some hash table key.

IOTA (N)

Generate a list of numbers between 0 and N-1.

IOTA+1 (N)

Generate a list of numbers between 1 and N.

IOTA-VECTOR (N)

Generate the equivalent of (COERCE (IOTA N) 'VECTOR).

LAST-TO-POSITION (SIZE NEW-POS)

Create a permutation that will permute the last element of a permutation of size SIZE to the position NEW-POS.

MAXIMUM (LIST &KEY (KEY 'IDENTITY))

Compute the maximum of LIST, optionally via the function KEY.

NSHUFFLE (VECTOR &OPTIONAL (PARITY ANY))

Shuffle the permutation vector VECTOR with specified parity PARITY. PARITY may be * :ANY for any permutation * :EVEN for only even permutations * :ODD for only odd permutations

PERM-EJECT (PERM)

Remove the largest element of a permutation.

PERM-EXTEND (PERM &OPTIONAL (N 1))

Extend a permutation PERM

PERM-GROUP.GENERATORS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

PERM-GROUP.STRONG-GENERATORS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

PERM-GROUP.TRANSVERSAL-SYSTEM (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

PERM-INJECT (PERM INJECT-TO)

For a permutation PERM of size N, inject N+1 to the position INJECT-TO.

PERM.SPEC (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

PRODUCT (SEQ &KEY (KEY 'IDENTITY))

Compute the product of the items in SEQ, optionally via the function KEY.

RANDOM-BETWEEN (A B)

Generate a random integer between A and B, inclusive.

RANDOM-HASH-TABLE-KEY (HASH-TABLE)

Obtain a random hash table key.

RANDOM-HASH-TABLE-VALUE (HASH-TABLE)

Obtain a random hash table value.

SAFE-GETHASH (KEY HASH-TABLE)

Throw an error in the event that KEY foes not exist in HASH-TABLE. Othwerwise return the value.

SIGN (X)

Return the sign of X.

SINGLETONP (X)

Does X contain one element?

Undocumented

%MAKE-PERM (&KEY ((SPEC DUM0) #(0)))

ABS> (X Y)

ADD-GENERATOR (PERM SGS TRANS &OPTIONAL (K (PERM-SIZE PERM)))

COPY-PERM (INSTANCE)

COPY-PERM-GROUP (INSTANCE)

EXISTS-MOBILE-P (PERM LEN)

MAKE-PERM-GROUP (&KEY ((GENERATORS DUM0) NIL) ((STRONG-GENERATORS DUM1) NIL) ((TRANSVERSAL-SYSTEM DUM2) NIL))

MOBILEP (IDX PERM &OPTIONAL (LEN (LENGTH PERM)))

NEXT-PERM (PERM LEN)

PERM-GROUP-P (OBJECT)

PERM-GROUP-PRINTER (GROUP STREAM DEPTH)

SETFPERM-GROUP.GENERATORS (NEW-VALUE INSTANCE)

SETFPERM-GROUP.STRONG-GENERATORS (NEW-VALUE INSTANCE)

SETFPERM-GROUP.TRANSVERSAL-SYSTEM (NEW-VALUE INSTANCE)

PERM-P (OBJECT)

PERM-READER (STREAM CHAR N)

REVERSE-DIRECTION (IDX PERM)

SAFE-SIGMA (TRANS K J)

TRANS-DECOMPOSITION (PERM TRANS &OPTIONAL (K (PERM-SIZE PERM)))

TRANS-ELEMENT-P (PERM TRANS &OPTIONAL (K (PERM-SIZE PERM)))

UPDATE-TRANSVERSAL (PERM SGS TRANS &OPTIONAL (K (PERM-SIZE PERM)))

MACRO

Public

DOPERMS ((X N &OPTIONAL RESULT) &BODY BODY)

Iterate over all permutations of size N, optionally returning RESULT.

GENERIC-FUNCTION

Private

Undocumented

HASH-TABLE-ACCESS-ERROR-KEY (CONDITION)

HASH-TABLE-ACCESS-ERROR-TABLE (CONDITION)

VARIABLE

Private

*PRINT-WITH-PERM-SYNTAX*

Print permutations with special permutation syntax?

CLASS

Public

Undocumented

PERM

PERM-GROUP

CONDITION

Private

HASH-TABLE-ACCESS-ERROR

An error to be signalled if a key doesn't exist in a hash-table.