The cl-permutation Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The cl-permutation Reference Manual

This is the cl-permutation Reference Manual, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:18:48 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

CL-PERMUTATION

A library for operating on permutations and permutation groups.

Creating Permutations

Permutations are represented by the structure PERM, which is read-only/immutable at the API boundary. A permutation of size N is essentially a sequence of numbers from 1 to N. One-based permutations were chosen because that is the dominating convention in mathematics. All we lose, essentially, is direct compatibility with array indexing, and one fixnum worth of space. (Internally, the permutations are stored in an array of size N+1, where the zeroth element is always zero).

A permutation can be created via MAKE-PERM:

PERM> (make-perm 1 2 3)
#<PERM 1 2 3>

The permutation will be checked for validity.

PERM> (make-perm 1 2 5)
Given permutation must contain the numbers 1 to 3
   [Condition of type SIMPLE-ERROR]

One can also create permutations with LIST-TO-PERM, which converts a list to a permutation. The companion function PERM-TO-LIST does the opposite operation, but it's not recommended to use list representations of permutations.

One can also create permutations with VECTOR-TO-PERM, which is analogous to LIST-TO-PERM, except it works for vectors. The reverse is PERM-TO-VECTOR.

Lastly, there is an experimental reader macro for permutations, which are created at read time. To enable the syntax, use

(enable-perm-reader)

and then one may type

#[3 1 2 4 5]

for permutations instead.

Permutation Operations

There is a slew of permutation operations:

Permutation Generation

There are ways of efficiently generating all permutations of a given length incrementally. Instead of generating all permutations at once in memory -- which takes O(n*n!) space -- we generate permutations on the fly.

The first way is to iterate over the permutations using a DOLIST-style macro called DOPERMS.

PERM> (let ((i 1))
        (doperms (p 3)
          (format t "~D: ~A~%" i p)
          (incf i)))
1: #<PERM 1 2 3>
2: #<PERM 1 3 2>
3: #<PERM 3 1 2>
4: #<PERM 3 2 1>
5: #<PERM 2 3 1>
6: #<PERM 2 1 3>

The other way is to produce a generator object (a closure, in fact) which generates the permutations. Simply FUNCALL the object to receive the next permutation. When they're all exhausted, the closure will return NIL.

PERM> (defparameter S3 (make-perm-generator 3))
S3
PERM> (defparameter S2 (make-perm-generator 2))
S2
PERM> (list (funcall S2) (funcall S3))
(#<PERM 1 2> #<PERM 1 2 3>)
PERM> (list (funcall S2) (funcall S3))
(#<PERM 2 1> #<PERM 1 3 2>)
PERM> (list (funcall S2) (funcall S3))
(NIL #<PERM 3 1 2>)
PERM> (list (funcall S2) (funcall S3))
(NIL #<PERM 3 2 1>)
PERM> (list (funcall S2) (funcall S3))
(NIL #<PERM 2 3 1>)

Cycle Operations

There's also a number of operations for cycles. Cycles are represented by the CYCLE structure. We can convert to and from cycle representation using TO-CYCLES and FROM-CYCLES. Cycles created by TO-CYCLES are automatically canonicalized with CANONICALIZE-CYCLES. Canonicalization is defined as:

Cycles that have not been canonicalized are printed with an asterisk '*'. We can observe this by explicitly disabling cycle canonicalization:

PERM> (make-cycle 3 1)
#<CYCLE (1 3)>                ; no asterisk
PERM> (let ((*canonicalize-cycle-on-creation* nil))
        (make-cycle 3 1))
#<CYCLE (3 1)*>               ; asterisk

An example use of TO-CYCLES is as follows:

PERM> (let ((r (random-perm 10)))
        (values r (to-cycles r)))
#<PERM 7 4 8 5 2 10 3 9 1 6>
(#<CYCLE (6 10)> #<CYCLE (2 4 5)> #<CYCLE (1 7 3 8 9)>)

FROM-CYCLES allows the specification of the permutation's length. For example:

PERM> (from-cycles (list (make-cycle 1 3 2)))
#<PERM 3 1 2>
PERM> (from-cycles (list (make-cycle 1 3 2)) 5)
#<PERM 3 1 2 4 5>

Lastly, there is a (mostly useless) function CYCLES-TO-ONE-LINE which converts cycles to one-line notation. That is, the cycles

(1 2 3)(4 5)

gets converted to the permutation

12345.

For example,

PERM> (cycles-to-one-line (list (make-cycle 1 2 3)
                                (make-cycle 4 5)))
#<PERM 1 2 3 4 5>

If one takes a permutation which has been canonically decomposed into cycles, then interestingly, there exists a bijection between one-line notation and the cycle decomposition.

Combinatorial Specifications

A "combinatorial specification" describes a space of combinatorial objects. They have a nice property that they all can be mapped to and from integers sharply. See the section "Ranking and Unranking Combinatorial Specifications".

Currently, only objects of linear structure exist. All of them are represented as subclasses of COMBINATORIAL-SPEC. They are as follows.

RADIX-SPEC: Base-B Non-Negative Integers

These are a representation of a base-B non-negative integer, for a base B > 1. They are handled by the RADIX-SPEC class. Within CL-PERMUTATION, the digits are written left-to-right to correspond with natural vector index ordering. A RADIX-SPEC can be made with MAKE-RADIX-SPEC. Here is the enumeration of all two-digit trinary numbers:

PERM> (print-objects-of-spec (make-radix-spec 3 2))
0 ==> #(0 0) ==> 0
1 ==> #(1 0) ==> 1
2 ==> #(2 0) ==> 2
3 ==> #(0 1) ==> 3
4 ==> #(1 1) ==> 4
5 ==> #(2 1) ==> 5
6 ==> #(0 2) ==> 6
7 ==> #(1 2) ==> 7
8 ==> #(2 2) ==> 8

MIXED-RADIX-SPEC: Non-Negative Mixed-Radix Integers

A mixed-radix integer is a generalization of a base-B integer. The digits in a mixed-radix numeral correspond to different bases. Mixed-radix specifications can be made with VECTOR-TO-MIXED-RADIX-SPEC. For example, the following are all numerals of radix (2, 3, 1):

PERM> (print-objects-of-spec (vector-to-mixed-radix-spec #(2 3 1)))
0 ==> #(0 0 0) ==> 0
1 ==> #(1 0 0) ==> 1
2 ==> #(0 1 0) ==> 2
3 ==> #(1 1 0) ==> 3
4 ==> #(0 2 0) ==> 4
5 ==> #(1 2 0) ==> 5

Notice again we use vector index ordering.

PERM-SPEC: Permutations

The space of permutations of length N (also known as S_N) can be represented. These are represented by the PERM-SPEC class.

PERM> (print-objects-of-spec (make-perm-spec 3))
0 ==> #(0 1 2) ==> 0
1 ==> #(0 2 1) ==> 1
2 ==> #(1 0 2) ==> 2
3 ==> #(1 2 0) ==> 3
4 ==> #(2 0 1) ==> 4
5 ==> #(2 1 0) ==> 5

Currently, actual PERM objects are not generated (see below about ranking/unranking). However, one can easily convert between the two.

COMBINATION-SPEC: Combinations

Combinations represent the selection of M objects from a collection of N objects. These are represented by a vector containing M 1's and N 0's. The class that manages this is a COMBINATION-SPEC. For example, all combinations of 2 objects of a total of 4 can be listed by the following:

PERM> (print-objects-of-spec (make-combination-spec 4 2))
0 ==> #(0 0 1 1) ==> 0
1 ==> #(0 1 0 1) ==> 1
2 ==> #(1 0 0 1) ==> 2
3 ==> #(0 1 1 0) ==> 3
4 ==> #(1 0 1 0) ==> 4
5 ==> #(1 1 0 0) ==> 5

WORD-SPEC: Words

A word is similar to a permutation except that it may have repeated, indistinct elements. These are represented by a WORD-SPEC. It can be created by supplying a sample word to the function VECTOR-TO-WORD-SPEC. For example, all words of the form 1123 can be listed as follows:

PERM> (print-objects-of-spec (vector-to-word-spec #(1 1 2 3)))
0 ==> #(1 1 2 3) ==> 0
1 ==> #(1 1 3 2) ==> 1
2 ==> #(1 2 1 3) ==> 2
3 ==> #(1 2 3 1) ==> 3
4 ==> #(1 3 1 2) ==> 4
5 ==> #(1 3 2 1) ==> 5
6 ==> #(2 1 1 3) ==> 6
7 ==> #(2 1 3 1) ==> 7
8 ==> #(2 3 1 1) ==> 8
9 ==> #(3 1 1 2) ==> 9
10 ==> #(3 1 2 1) ==> 10
11 ==> #(3 2 1 1) ==> 11

Ranking and Unranking Combinatorial Specifications

Each combinatorial specification represents a finite space of N > 0 objects. N is called the "cardinality" of the specification and can be computed with the CARDINALITY method.

> (cardinality (make-perm-spec 3))
6
> (cardinality (vector-to-word-spec #(1 1 2 3)))
12

The cardinality is computed only once for a combinatorial specification and is then cached for fast access.

Obviously, every object in a particular finite combinatorial space can be bijected to and from integers below the cardinality of that space. CL-PERMUTATION provides fast and efficient mechanisms for computing one such bijection for each combinatorial specification. Mapping from an object to an integer is called "ranking" and mapping from an integer back to an object is called "unranking".

When a lexicographic ordering makes sense, there will be 1-to-1 correspondence with the ordering on integers. In other words for objects X1 and X2 and their ranks R1 and R2, X1 lex< X2 iff R1 < R2.

The method UNRANK takes a combinatorial specification and an integer, and maps it to the corresponding object representation (usually a vector). It takes an optional keyword argument :SET which acts as a destination of the unranked object (for efficiency purposes).

The method RANK takes a combinatorial specification and an object produced by UNRANK (again, usually a sensible vector) and returns the integer (the "rank") of that object. PRINT-OBJECTS-OF-SPEC, as used above, prints the rank of every object in a combinatorial space.

One can map over all objects and ranks by using MAP-SPEC, which takes a binary function (rank and object) as well as a combinatorial specification, and applies that function to each object and their rank.

Permutation Groups

There is initial support for permutation groups at the moment. Permutation groups are represented by the structure PERM-GROUP.

We can create a permutation group from its generators via GENERATE-PERM-GROUP. A shorthand syntax is provided which, instead of taking a list of PERM objects, takes a list of lists representing perms. This shorthand is GROUP-FROM. For example, the following two are the same group:

PERM> (generate-perm-group (list (make-perm 1 3 2 4)
                                 (make-perm 3 2 4 1)))
#<PERM-GROUP of 2 generators>
PERM> (group-from '((1 3 2 4)
                    (3 2 4 1)))
#<PERM-GROUP of 2 generators>

We can generate a permutation group from a list of cycles as well. The above is equivalent to

PERM> (group-from-cycles (list (list (make-cycle 2 3))
                               (list (make-cycle 1 3 4)))
                         4) 
#<PERM-GROUP of 2 generators>

Once we have generated a group, we can do some operations on it.

For example, let's define the group for 3x3 Rubik's cubes. A cube has six moves: we can turn the front, back, left, right, top, and bottom. Label each sticker with a number like so:

                     +--------------+
                     |              |
                     |  1    2    3 |
                     |              |
                     |  4   up    5 |
                     |              |
                     |  6    7    8 |
                     |              |
      +--------------+--------------+--------------+--------------+
      |              |              |              |              |
      |  9   10   11 | 17   18   19 | 25   26   27 | 33   34   35 |
      |              |              |              |              |
      | 12  left  13 | 20 front  21 | 28 right  29 | 36  back  37 |
      |              |              |              |              |
      | 14   15   16 | 22   23   24 | 30   31   32 | 38   39   40 |
      |              |              |              |              |
      +--------------+--------------+--------------+--------------+
                     |              |
                     | 41   42   43 |
                     |              |
                     | 44  down  45 |
                     |              |
                     | 46   47   48 |
                     |              |
                     +--------------+

Each turn corresponds to a permutation of stickers. I'll do the hard work of specifying them:

(defparameter rubik-3x3
  (group-from
   '((3 5 8 2 7 1 4 6 33 34 35 12 13 14 15 16 9 10 11 20 21 22 23 24 17 
      18 19 28 29 30 31 32 25 26 27 36 37 38 39 40 41 42 43 44 45 46 47 48)
     (17 2 3 20 5 22 7 8 11 13 16 10 15 9 12 14 41 18 19 44 21 46 23 24 
      25 26 27 28 29 30 31 32 33 34 6 36 4 38 39 1 40 42 43 37 45 35 47 48) 
     (1 2 3 4 5 25 28 30 9 10 8 12 7 14 15 6 19 21 24 18 23 17 20 22 43 
      26 27 42 29 41 31 32 33 34 35 36 37 38 39 40 11 13 16 44 45 46 47 48) 
     (1 2 38 4 36 6 7 33 9 10 11 12 13 14 15 16 17 18 3 20 5 22 23 8 27 
      29 32 26 31 25 28 30 48 34 35 45 37 43 39 40 41 42 19 44 21 46 47 24) 
     (14 12 9 4 5 6 7 8 46 10 11 47 13 48 15 16 17 18 19 20 21 22 23 24
      25 26 1 28 2 30 31 3 35 37 40 34 39 33 36 38 41 42 43 44 45 32 29 27) 
     (1 2 3 4 5 6 7 8 9 10 11 12 13 22 23 24 17 18 19 20 21 30 31 32 25
      26 27 28 29 38 39 40 33 34 35 36 37 14 15 16 43 45 48 42 47 41 44 46))))

Now we have our group:

PERM> rubik-3x3
#<PERM-GROUP of 6 generators>

Let's query the group's order:

PERM> (group-order rubik-3x3)
43252003274489856000

A lot of positions! Let's generate a random cube:

PERM> (random-group-element rubik-3x3)
#<PERM 1 20 24 39 12 40 29 41 9 47 46 21 45 11 34 8 14 36 22 31 44 25 10 48
       16 37 43 15 26 32 7 33 30 13 35 5 28 27 23 17 19 4 38 2 18 6 42 3>

And as cycles...

PERM> (to-cycles *)
(#<CYCLE (35)>
 #<CYCLE (30 32 33)>
 #<CYCLE (27 43 38)>
 #<CYCLE (9)>
 #<CYCLE (8 41 19 22 25 16)>
 #<CYCLE (6 40 17 14 11 46)>
 #<CYCLE (4 39 23 10 47 42)>
 #<CYCLE (3 24 48)>
 #<CYCLE (2 20 31 7 29 26 37 28 15 34 13 45 18 36 5 12 21 44)>
 #<CYCLE (1)>)

Let's check if flipping an edge piece is valid:

PERM> (group-element-p (from-cycles (list (make-cycle 7 18)) 48) rubik-3x3)
NIL

No it's not. How about four edge pieces?

PERM> (group-element-p (from-cycles (list (make-cycle 7 18)
                                          (make-cycle 2 34)
                                          (make-cycle 4 10)
                                          (make-cycle 5 26))
                                    48)
                       rubik-3x3)
T

As can be seen, the few operations we have are powerful in studying finite groups.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 cl-permutation

Author

Robert Smith <robert@stylewarning.com>

License

BSD 3-clause (See LICENSE)

Description

A library for operating on permutations and permutation groups.

Dependencies
Source

cl-permutation.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 cl-permutation.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/cl-permutation-20180228-git/cl-permutation.asd

Systems

cl-permutation (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 cl-permutation/package.lisp

Parent

cl-permutation (system)

Location

package.lisp

Packages

cl-permutation


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 cl-permutation/utilities.lisp

Dependency

package.lisp (file)

Parent

cl-permutation (system)

Location

utilities.lisp

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.4 cl-permutation/permutation.lisp

Dependency

utilities.lisp (file)

Parent

cl-permutation (system)

Location

permutation.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.5 cl-permutation/bruhat.lisp

Dependency

permutation.lisp (file)

Parent

cl-permutation (system)

Location

bruhat.lisp

Exported Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.6 cl-permutation/permutation-generation.lisp

Dependency

bruhat.lisp (file)

Parent

cl-permutation (system)

Location

permutation-generation.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.7 cl-permutation/group.lisp

Dependency

permutation-generation.lisp (file)

Parent

cl-permutation (system)

Location

group.lisp

Exported Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.8 cl-permutation/free-group.lisp

Dependency

group.lisp (file)

Parent

cl-permutation (system)

Location

free-group.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.9 cl-permutation/straight-line-program.lisp

Dependency

free-group.lisp (file)

Parent

cl-permutation (system)

Location

straight-line-program.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.10 cl-permutation/permutation-group.lisp

Dependency

straight-line-program.lisp (file)

Parent

cl-permutation (system)

Location

permutation-group.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.11 cl-permutation/homomorphism.lisp

Dependency

permutation-group.lisp (file)

Parent

cl-permutation (system)

Location

homomorphism.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.12 cl-permutation/orbit.lisp

Dependency

homomorphism.lisp (file)

Parent

cl-permutation (system)

Location

orbit.lisp

Exported Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.13 cl-permutation/do-group-elements.lisp

Dependency

orbit.lisp (file)

Parent

cl-permutation (system)

Location

do-group-elements.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.14 cl-permutation/block.lisp

Dependency

do-group-elements.lisp (file)

Parent

cl-permutation (system)

Location

block.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.15 cl-permutation/combinatorial-ranking.lisp

Dependency

block.lisp (file)

Parent

cl-permutation (system)

Location

combinatorial-ranking.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.16 cl-permutation/find-subgroups.lisp

Dependency

combinatorial-ranking.lisp (file)

Parent

cl-permutation (system)

Location

find-subgroups.lisp

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.17 cl-permutation/god.lisp

Dependency

find-subgroups.lisp (file)

Parent

cl-permutation (system)

Location

god.lisp

Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.18 cl-permutation/extra-functions.lisp

Dependency

god.lisp (file)

Parent

cl-permutation (system)

Location

extra-functions.lisp

Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 cl-permutation

Source

package.lisp (file)

Nickname

perm

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Special variables

Special Variable: *canonicalize-cycle-on-creation*
Package

cl-permutation

Source

permutation.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Macros

Macro: do-group-elements (VAR GROUP &optional RETURN) &body BODY

Iterate through all of the elements of the group GROUP, binding each element to VAR and executing BODY. Optionally return a value specified by RETURN.

Package

cl-permutation

Source

do-group-elements.lisp (file)

Macro: doperms (X N &optional RESULT) &body BODY

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

Package

cl-permutation

Source

permutation-generation.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Functions

Function: bruhat< W V

Does W precede V in the Bruhat sense?

We say that W precedes V in the Bruhat sense if there’s a transposition S with V = WS and the length of V is one less the length of W.

Package

cl-permutation

Source

bruhat.lisp (file)

Function: bruhat<= W V

Does W precede V in the Bruhat sense, or are they equal?

Package

cl-permutation

Source

bruhat.lisp (file)

Function: canonicalize-cycle CYCLE

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: canonicalize-cycles CYCLES

Canonicalize each cycle in the list of cycles CYCLES, then canonicalize the list of cycles in descending value of the first position of the cycle.

Package

cl-permutation

Source

permutation.lisp (file)

Function: compose-slp SLP1 SLP2

Compose two SLPs SLP1 and SLP2.

Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: cycle-identity-p CYCLE

Is the cycle CYCLE representative of an identity permutation?

Package

cl-permutation

Source

permutation.lisp (file)

Function: cycle-length CYCLE

Compute the length of the cycle CYCLE.

Package

cl-permutation

Source

permutation.lisp (file)

Function: cycle-ref CYCLE N

Compute the Nth element of the cycle CYCLE. Treat the cycle as if it is circular (so indexes greater than the cycle length or less than zero will wrap around).

Package

cl-permutation

Source

permutation.lisp (file)

Function: cycle-type PERM

Compute the cycle type of a perm PERM.

The cycle type is a partition of the perm’s size, and is equal to the lengths of the cycles in descending order of the perm’s cycle decomposition.

Package

cl-permutation

Source

permutation.lisp (file)

Function: cycles-to-one-line CYCLES

Convert CYCLES to one-line notation. This is the same as flattening the cycles.

Note: This is not the same as FROM-CYCLES.

Package

cl-permutation

Source

permutation.lisp (file)

Function: enable-perm-reader ()

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: evaluate-slp GROUP CTX SLP &key HOMOMORPHISM

Within a group GROUP, and given the context CTX and the straight line program SLP, compute its evaluation (the value of the SLP in the target group).

If HOMOMORPHISM is provided, then the image of each SLP-ELEMENT will be computed. The image of the homomorphism should be GROUP.

Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: find-conjugator X Y

Find an element that conjugates X to Y. In other words, find the permutation C such that

Y = C X C^-1.

Package

cl-permutation

Source

permutation.lisp (file)

Function: find-minimal-block-system-containing PERM-GROUP ALPHAS

Find the minimal blocks of the permutation group PERM-GROUP which contain the list of points ALPHAS.

Returns a list of lists. Each sub-list represents a block. Each block is an image of one another under the generators of the group.

Package

cl-permutation

Source

block.lisp (file)

Function: find-non-trivial-block-system GROUP

Find a non-trivial block system of the permutation group GROUP.

GROUP must be transitive in order for this to produce truly non-trivial block systems.

Package

cl-permutation

Source

block.lisp (file)

Function: free-group-identity-p X

Is X an identity element of a free group?

Package

cl-permutation

Source

free-group.lisp (file)

Function: from-cycles CYCLES &optional SIZE

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

SIZE is ignored if it is less than the maximum point within the cycles.

Package

cl-permutation

Source

permutation.lisp (file)

Function: generate-perm-group GENERATORS

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

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: generator-decomposition G GROUP &key RETURN-ORIGINAL-GENERATORS

Given an element g ∈ GROUP, factorize it into a sequence of generators, represented as a list of elements in the homomorphic FREE-GROUP.

If RETURN-ORIGINAL-GENERATORS is true, return the group’s original generators as permutations.

This is also called "factorization".

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: group-degree GROUP &key TRUE

What is the degree of the group GROUP?

If TRUE is a true-value, then the true degree will be returned (i.e., the maximum non-fixed point index). For example, consider

G = <(1 3 2 4 5)>

then

(group-degree G :true nil) ==> 5 [default]
(group-degree G :true t) ==> 3.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: group-element-p PERM GROUP

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

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: group-element-rank-functions GROUP

Generate two functions as values:

1. A function to map elements of the permutation group GROUP to integers [0, 2^|GROUP| - 1].

2. The inverse of the above function.

Package

cl-permutation

Source

do-group-elements.lisp (file)

Function: group-from GENERATORS-AS-LISTS

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

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: group-from-cycles GENERATORS-AS-CYCLES SIZE

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

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: group-from-orbit ORIGINAL-GROUP ORBIT

Produce a group by having the group ORIGINAL-GROUP act on the orbit ORBIT of that group.

As a second value, the homomorphism will be returned.

Package

cl-permutation

Source

orbit.lisp (file)

Function: group-identity GROUP

Return the identity element of the group GROUP.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: group-orbits GROUP

Compute the orbits of the group GROUP. This will be a list of arrays of points.

Package

cl-permutation

Source

orbit.lisp (file)

Function: group-order GROUP

Compute the order of the permutation group GROUP.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: homomorphism-induced-perm-group GROUP HOM

Given a group GROUP, and a homomorphism HOM mapping elements of that group to permutations,compute the homomorphism-induced group.

Package

cl-permutation

Source

homomorphism.lisp (file)

Function: invert-slp SLP

Invert the SLP SLP.

Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: list-to-perm LIST

Construct a perm from a list LIST.

Package

cl-permutation

Source

permutation.lisp (file)

Function: make-combination-spec N M

Make a COMBINATION-SPEC representing the space of objects representing M items being chosen out of N total.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: make-cycle &rest ELEMENTS

Create a new cycle with the elements ELEMENTS.

Package

cl-permutation

Source

permutation.lisp (file)

Function: make-free-group NUM-GENERATORS

Make a free group that contains NUM-GENERATORS generators.

Package

cl-permutation

Source

free-group.lisp (file)

Function: make-free-group-element G &rest ELEMENTS

Make an element of the free group G where ELEMENTS are either integer generators of G, or other elements created by this function.

Package

cl-permutation

Source

free-group.lisp (file)

Function: make-perm &rest ELEMENTS

Construct a permutation from the numbers ELEMENTS.

Package

cl-permutation

Source

permutation.lisp (file)

Function: make-perm-generator N

Create a generator that generates permutations of size N.

Package

cl-permutation

Source

permutation-generation.lisp (file)

Function: make-perm-spec N

Make a PERM-SPEC representing the set of permutations S_n.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: make-radix-spec RADIX SIZE

Make a RADIX-SPEC representing all numbers between 0 and RADIX^SIZE - 1.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: map-spec F SPEC

Call the function F across all elements described by SPEC.

F should be a binary function whose first argument represents the rank of object passed as the second argument.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: naive-generator-decomposition PERM GROUP &key RETURN-ORIGINAL-GENERATORS

Compute the generator decomposition of the permutation PERM of the group GROUP. By default, return a sequence of free generators.

If RETURN-ORIGINAL-GENERATORS is true, return the group’s original generators as permutations.

Note: The result is likely very long and inefficient.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: orbit-group-homomorphism ORIGINAL-GROUP ORBIT

Compute a homomorphism between elements of the permutation group ORIGINAL-GROUP to the naturally induced group of an orbit ORBIT of ORIGINAL-GROUP.

Package

cl-permutation

Source

orbit.lisp (file)

Function: orbit-length N PERM

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: orbit-of N PERM

Compute the orbit of the element N in the permutation PERM. Return a cycle representing the orbit of N.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-compose P1 P2

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

Example: If P1 = 2 |-> 3 and P2 = 1 |-> 2 then (perm-compose P1 P2) = 1 |-> 3.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-compose-flipped P1 P2

Compose the permutatons P1 and P2: x |-> P2(P1(x)). This is equivalent to (PERM-COMPOSE P2 P1).

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-conjugate P C

Conjugate the permutation P by G. This is G P G^-1.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-eval PERM N

Evaluate the permutation PERM at index N.

Package

cl-permutation

Source

permutation.lisp (file)

Function: 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.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-evaluator PERM

Return an evaluation function for the permutation PERM (a la PERM-EVAL).

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-evaluator* PERM

Return an evaluation function for the permutation PERM (a la PERM-EVAL*).

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-even-p PERM

Is PERM an even permutation?

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-expt PERM N

Raise a permutation PERM to the Nth power. If N is negative, then the inverse will be raised to the -Nth power.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-fixpoints PERM &optional N

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-identity N

The identity permutation of size N.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-identity-p PERM

Is the permutation PERM an identity permutation?

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-inverse PERM

Find the inverse of the permutation PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-inverse-eval PERM N

Evaluate the inverse of the permutation PERM at index N.

Package

cl-permutation

Source

permutation.lisp (file)

Function: 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.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-last-non-fixpoint PERM

Find the last non-fixed point of the perm PERM. If it exists, return the index A and the point B as two values. These satisfy

(PERM-EVAL PERM A) = B

If a fixed point doesn’t exist, return NIL.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-length PERM

Count the number of inversions in the permutation PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-odd-p PERM

Is PERM an odd permutation?

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-order PERM

Compute the order of a permutation PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-point-fixed-p PERM K

Is K fixed in the perm PERM?

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-ref PERM N

Compute the zero-based index of PERM at N.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-sign PERM

The sign of a permutation PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-size PERM

The size of a permutation PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-to-list PERM

Convert a permutation PERM to a list representation.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-to-vector PERM

Convert a permutation PERM to a vector.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-transpose-entries PERM A B

Transpose the entries A and B in PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-transpose-indexes PERM A B

Transpose the indexes A and B in PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm= PERM OTHER-PERM

Are PERM and OTHER-PERM mathematically equal? (Note: Different sized perms are considered unequal. See PERM=* for extended equality.)

Package

cl-permutation

Source

permutation.lisp (file)

Function: perm=* PERM OTHER-PERM

Are PERM and OTHER-PERM mathematically equal when viewed as functions on naturals? (Note: For inequality on different sized perms, see PERM=.)

Package

cl-permutation

Source

permutation.lisp (file)

Function: permute PERM A &key TYPE

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: primitive-group-p GROUP

Is the perm group GROUP primitive?

Package

cl-permutation

Source

block.lisp (file)

Function: print-objects-of-spec SPEC &optional STREAM

Given the combinatorial specification SPEC, enumerate all possible objects represented by that specification, printing them to the stream STREAM.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: random-group-element GROUP

Generate a random element of the group GROUP.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: random-perm N &optional PARITY

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: rotate-cycle CYCLE &optional N

Rotate the elements of a cycle CYCLE syntactically counterclockwise/left, a total of N times. When N is negative, rotate in the opposite direction. Return a fresh cycle.

Package

cl-permutation

Source

permutation.lisp (file)

Function: slp-composition %0 %1
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: slp-element %0
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: slp-inversion %0
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: slp-symbol %0
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: subdirect-factors GROUP

Compute "subdirect factors" of the group GROUP.

These are groups whose direct product has GROUP as a subgroup.

As a second value, return the corresponding list of homomorphisms between GROUP and the subdirect factors.

Package

cl-permutation

Source

orbit.lisp (file)

Function: subgroup-p GROUP SUBGROUP

Is the group SUBGROUP a subgroup of GROUP?

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: symbol-assignment CTX SYMBOL

Within the context CTX and the symbol SYMBOL, look up its representation. Return NIL if it does not exist.

Package

cl-permutation

Source

straight-line-program.lisp (file)

Writer

(setf symbol-assignment) (function)

Function: (setf symbol-assignment) REPRESENTATION CTX SYMBOL

Assign to the symbol SYMBOL the representation REPRESENTATION within the context CTX.

Package

cl-permutation

Source

straight-line-program.lisp (file)

Reader

symbol-assignment (function)

Function: to-cycles PERM &key CANONICALIZEP

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: transversal-decomposition PERM GROUP &key REMOVE-IDENTITIES

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

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: vector-to-mixed-radix-spec RADIX

Make a MIXED-RADIX-SPEC representing all mixed-radix numbers specified by the vector RADIX.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: vector-to-perm WORD

Convert a vector VECTOR to a permutation. VECTOR must represent a valid elements of a permutation.

Package

cl-permutation

Source

permutation.lisp (file)

Function: vector-to-word-spec WORD

WORD should be a vector containing 1, 2, ..., N, possibly with repeated elements.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.4 Generic functions

Generic Function: cardinality SPEC

Compute the cardinality of SPEC. This represents the total number of elements described by the spec.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Methods
Method: cardinality (SPEC word-spec)
Method: cardinality (SPEC combination-spec)
Method: cardinality (SPEC perm-spec)
Method: cardinality (SPEC mixed-radix-spec)
Method: cardinality (SPEC radix-spec)
Method: cardinality (SPEC combinatorial-spec) around
Generic Function: compose G A B

Compose two elements A and B within the group G.

Package

cl-permutation

Source

group.lisp (file)

Methods
Method: compose (G perm-group) A B
Source

permutation-group.lisp (file)

Method: compose (G free-group) A B
Source

free-group.lisp (file)

Generic Function: generators G

Return a list of the generators of G.

Package

cl-permutation

Source

group.lisp (file)

Methods
Method: generators (G perm-group)
Source

permutation-group.lisp (file)

Method: generators (G free-group)
Source

free-group.lisp (file)

Generic Function: homomorphism-image HOM

Image group of the homomorphism HOM.

Package

cl-permutation

Source

homomorphism.lisp (file)

Methods
Method: homomorphism-image (GENERATOR-HOMOMORPHISM generator-homomorphism)

Image of the homomorphism.

Method: homomorphism-image (FUNCTION-HOMOMORPHISM function-homomorphism)

Image of the homomorphism.

Generic Function: homomorphism-preimage HOM

Preimage group of the homomorphism HOM.

Package

cl-permutation

Source

homomorphism.lisp (file)

Methods
Method: homomorphism-preimage (GENERATOR-HOMOMORPHISM generator-homomorphism)

Preimage of the homomorphism.

Method: homomorphism-preimage (FUNCTION-HOMOMORPHISM function-homomorphism)

Preimage of the homomorphism.

Generic Function: identity-element G

Return the identity element of the group G.

Package

cl-permutation

Source

group.lisp (file)

Methods
Method: identity-element (G perm-group)
Source

permutation-group.lisp (file)

Method: identity-element (G free-group)
Source

free-group.lisp (file)

Generic Function: image HOMOMORPHISM OBJECT

Compute the image of object OBJECT with respect to the homomorphism HOMOMORPHISM.

Package

cl-permutation

Source

homomorphism.lisp (file)

Methods
Method: image (HOM generator-homomorphism) (ELT perm)

Given a homomorphism HOM, compute the image of ELT.

Method: image (HOM function-homomorphism) OBJ
Method: image (HOM function) OBJECT
Generic Function: inverse G A

Compute the inverse of A within the group G.

Package

cl-permutation

Source

group.lisp (file)

Methods
Method: inverse (G perm-group) A
Source

permutation-group.lisp (file)

Method: inverse (G free-group) A
Source

free-group.lisp (file)

Generic Function: num-generators G

Return the number of generators of the group G.

Package

cl-permutation

Source

group.lisp (file)

Methods
Method: num-generators (G perm-group)
Source

permutation-group.lisp (file)

Method: num-generators (G free-group)
Source

free-group.lisp (file)

Generic Function: radix OBJECT
Package

cl-permutation

Methods
Method: radix (MIXED-RADIX-SPEC mixed-radix-spec)

automatically generated reader method

Source

combinatorial-ranking.lisp (file)

Method: radix (RADIX-SPEC radix-spec)

automatically generated reader method

Source

combinatorial-ranking.lisp (file)

Generic Function: rank SPEC SET

Rank the set SET to an integer according to the spec SPEC.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Methods
Method: rank (SPEC word-spec) SET
Method: rank (SPEC combination-spec) SET
Method: rank (SPEC perm-spec) SET
Method: rank (SPEC mixed-radix-spec) SET
Method: rank (SPEC radix-spec) SET
Generic Function: size OBJECT
Package

cl-permutation

Methods
Method: size (COMBINATORIAL-SPEC combinatorial-spec)

automatically generated reader method

Source

combinatorial-ranking.lisp (file)

Generic Function: unrank SPEC IDX &key SET

Unrank the integer rank IDX according to SPEC. If SET is provided, such a vector will be filled. Otherwise, one will be allocated. (Beware: SET must be a vector of an appropriate size.)

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Methods
Method: unrank (SPEC word-spec) (IDX integer) &key SET
Method: unrank (SPEC combination-spec) (IDX integer) &key SET
Method: unrank (SPEC perm-spec) (IDX integer) &key SET
Method: unrank (SPEC mixed-radix-spec) (IDX integer) &key SET
Method: unrank (SPEC radix-spec) (IDX integer) &key SET

Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.5 Structures

Structure: cycle ()
Package

cl-permutation

Source

permutation.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: canonicalized
Type

boolean

Readers

cycle-canonicalized (function)

Writers

(setf cycle-canonicalized) (function)

Slot: rep
Type

(vector cl-permutation:cycle-element)

Initform

#()

Readers

cycle-rep (function)

Writers

(setf cycle-rep) (function)

Structure: perm ()
Package

cl-permutation

Source

permutation.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods
  • image (method)
  • print-object (method)
Direct slots
Slot: rep
Type

cl-permutation::raw-perm

Initform

(cl-permutation::iota-vector 1)

Readers

perm.rep (function)

Writers

(setf perm.rep) (function)

Structure: slp ()
Package

cl-permutation

Source

straight-line-program.lisp (file)

Direct superclasses

algebraic-data-type (structure)

Direct subclasses
Structure: slp-composition ()
Package

cl-permutation

Source

straight-line-program.lisp (file)

Direct superclasses

slp (structure)

Direct methods
  • make-load-form (method)
  • print-object (method)
Direct slots
Slot: %0
Type

cl-permutation:slp

Initform

(error "unspecified field.")

Readers

slp-composition%0 (function)

Writers

(setf slp-composition%0) (function)

Slot: %1
Type

cl-permutation:slp

Initform

(error "unspecified field.")

Readers

slp-composition%1 (function)

Writers

(setf slp-composition%1) (function)

Structure: slp-element ()
Package

cl-permutation

Source

straight-line-program.lisp (file)

Direct superclasses

slp (structure)

Direct methods
  • make-load-form (method)
  • print-object (method)
Direct slots
Slot: %0
Initform

(error "unspecified field.")

Readers

slp-element%0 (function)

Writers

(setf slp-element%0) (function)

Structure: slp-inversion ()
Package

cl-permutation

Source

straight-line-program.lisp (file)

Direct superclasses

slp (structure)

Direct methods
  • make-load-form (method)
  • print-object (method)
Direct slots
Slot: %0
Type

cl-permutation:slp

Initform

(error "unspecified field.")

Readers

slp-inversion%0 (function)

Writers

(setf slp-inversion%0) (function)

Structure: slp-symbol ()
Package

cl-permutation

Source

straight-line-program.lisp (file)

Direct superclasses

slp (structure)

Direct methods
  • make-load-form (method)
  • print-object (method)
Direct slots
Slot: %0
Type

symbol

Initform

(error "unspecified field.")

Readers

slp-symbol%0 (function)

Writers

(setf slp-symbol%0) (function)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.6 Classes

Class: combination-spec ()

Representation of a sequence

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Direct superclasses

combinatorial-spec (class)

Direct methods
Direct slots
Slot: zero-count
Initargs

:zero-count

Readers

comb.zero-count (generic function)

Class: combinatorial-spec ()

Abstract class representing linear sequences of objects of size SIZE.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses
Direct methods
Direct slots
Slot: cardinality-cache
Type

(or null unsigned-byte)

Readers

cardinality-cache (generic function)

Writers

(setf cardinality-cache) (generic function)

Slot: size
Initargs

:size

Readers

size (generic function)

Class: free-group ()

Representation of a free group whose symbols are:

* identity element: 0
* generators: 1 .. N
* inverse generators: -N .. -1

Elements of the group are either individual integers or lists thereof. The lists represent compositions of generators. The BNF grammar looks something like:

<free group generator> := 1 | 2 | ... | N
<free group atom> := <free group generator>
| 0
| -<free group generator>
<free group element> := <free group atom>
| ( <free group atom>* )

An empty list corresponds to an empty composition, which is identity (0).

Package

cl-permutation

Source

free-group.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: num-generators
Initargs

:num-generators

Readers

free-group-num-generators (generic function)

Class: function-homomorphism ()

Simple class which wraps homomorphic functions, associating them with the preimage and image of the function.

Package

cl-permutation

Source

homomorphism.lisp (file)

Direct superclasses

homomorphism (class)

Direct methods
Direct slots
Slot: from-group

Preimage of the homomorphism.

Initargs

:from-group

Readers

homomorphism-preimage (generic function)

Slot: to-group

Image of the homomorphism.

Initargs

:to-group

Readers

homomorphism-image (generic function)

Slot: function

Homomorphism function.

Initargs

:function

Readers

homomorphism-function (generic function)

Class: generator-homomorphism ()

A perm group homomorphism constructed from images of its genertators.

This class is FUNCALLable.

Package

cl-permutation

Source

homomorphism.lisp (file)

Direct superclasses

homomorphism (class)

Direct methods
Direct slots
Slot: from-group

Preimage of the homomorphism.

Initargs

:from-group

Readers

homomorphism-preimage (generic function)

Slot: to-group

Image of the homomorphism.

Initargs

:to-group

Readers

homomorphism-image (generic function)

Slot: generator-map

A unary function mapping generators of FROM-GROUP to objects of the resulting group TO-GROUP.

Initargs

:generator-map

Readers

homomorphism-generator-map (generic function)

Class: mixed-radix-spec ()

Representation of a mixed-radix number of size SIZE with mixed radix RADIX.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Direct superclasses

combinatorial-spec (class)

Direct methods
Direct slots
Slot: radix
Initargs

:radix

Readers

radix (generic function)

Class: perm-group ()

Representation of a permutation group generated by a finite number of generators.

Package

cl-permutation

Source

permutation-group.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: element-size

The size of the elements of the group. This is a non-negative integer and may be larger than the true degree of the group.

Initargs

:element-size

Readers

perm-group.element-size (generic function)

Writers

(setf perm-group.element-size) (generic function)

Slot: generators

A list of generators of the group.

Initargs

:generators

Readers

perm-group.generators (generic function)

Writers

(setf perm-group.generators) (generic function)

Slot: strong-generators

The strong generating set of the group. This is a vector mapping integers to lists of generators which generate the i’th stabilizer.

Initargs

:strong-generators

Readers

perm-group.strong-generators (generic function)

Writers

(setf perm-group.strong-generators) (generic function)

Slot: transversal-system

The transversal system of the group. This is a vector mapping integers K to a table of sigmas SIGMA_K. Every permutation in the group can be represented by a product of permutations SIGMA_K * ... * SIGMA_2 * SIGMA_1.

Initargs

:transversal-system

Readers

perm-group.transversal-system (generic function)

Writers

(setf perm-group.transversal-system) (generic function)

Slot: free-group

A free group corresponding to the given permutation group.

Initargs

:free-group

Readers

perm-group.free-group (generic function)

Writers

(setf perm-group.free-group) (generic function)

Slot: factorization-generators

A vector whose length is the same length as the base of the group, whose values are vectors of free-group elements that are coset representatives of the stabilizer G^(i+1)/G^(i). This collection of generators is *also* a strong generating set. This is optionally computed with #’COMPUTE-FACTORIZATION-GENERATORS.

Initargs

:factorization-generators

Readers

perm-group.factorization-generators (generic function)

Writers

(setf perm-group.factorization-generators) (generic function)

Slot: slp-context

SLPs corresponding to all sigmas and strong generators.

Initargs

:slp-context

Readers

perm-group.slp-context (generic function)

Writers

(setf perm-group.slp-context) (generic function)

Class: perm-spec ()

Representation of a perm of size SIZE. Canonically this is a permutation of the set {1, ..., SIZE}. (Though it’s possible to rank the permutation of any subset of numbers.)

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Direct superclasses

combinatorial-spec (class)

Direct methods
Class: radix-spec ()

Representation of a sequence of numbers of length SIZE whose elements are between 0 and RADIX - 1.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Direct superclasses

combinatorial-spec (class)

Direct methods
Direct slots
Slot: radix
Initargs

:radix

Readers

radix (generic function)

Class: slp-context ()

Represents a context (e.g., symbol assignments) in which an SLP can be evaluated.

Package

cl-permutation

Source

straight-line-program.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: symbol-table

A mapping between symbols and their representation as SLPs.

Initform

(make-hash-table :test (quote eq))

Readers

symbol-table (generic function)

Writers

(setf symbol-table) (generic function)

Class: word-spec ()

Representation of a word of elements 1 to TYPES.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Direct superclasses

combinatorial-spec (class)

Direct methods
Direct slots
Slot: types

Non-negative integer representing the number of distinct elements within the word. Note that this will include the additional zero type, even though there are never any zero elements.

Initargs

:types

Readers

word.types (generic function)

Slot: type-counts

Vector of non-negative integers representing the count of each individual element type. (The sum of this vector should equal TYPES.)

Initargs

:type-counts

Readers

word.type-counts (generic function)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.7 Types

Type: cycle-element ()

An element of a cycle.

Package

cl-permutation

Source

permutation.lisp (file)

Type: perm-element ()

An element of a perm.

Package

cl-permutation

Source

permutation.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Special variables

Special Variable: *context*

Special variable used to hold the context being built up for a group.

Package

cl-permutation

Source

permutation-group.lisp (file)

Special Variable: *perm-group-verbose*
Package

cl-permutation

Source

permutation-group.lisp (file)

Special Variable: *print-with-perm-syntax*

Print permutations with special permutation syntax?

Package

cl-permutation

Source

permutation.lisp (file)

Special Variable: *taus*

Special variable used to hold a mapping between permutation objects (by EQ) to a symbol (one generated by #’TAU-SYMBOL) which is referred to by the SLP context.

Package

cl-permutation

Source

permutation-group.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Functions

Function: %compute-factorization-generators GROUP &key MAX-ROUNDS IMPROVE-EVERY L
Package

cl-permutation

Source

permutation-group.lisp (file)

Function: %make-cycle &key (CANONICALIZED CANONICALIZED) (REP REP)
Package

cl-permutation

Source

permutation.lisp (file)

Function: %make-djs &key (REPRESENTATIVE REPRESENTATIVE) (VALUE VALUE)
Package

cl-permutation

Source

block.lisp (file)

Function: %make-djs-rep &key (DJS DJS)
Package

cl-permutation

Source

block.lisp (file)

Function: %make-perm &key (REP REP)
Package

cl-permutation

Source

permutation.lisp (file)

Function: %make-queue &key (ELEMENTS ELEMENTS) (LAST LAST)
Package

cl-permutation

Source

utilities.lisp (file)

Function: %perm-compose-upto P1 P2 N
Package

cl-permutation

Source

permutation.lisp (file)

Function: abs> X Y
Package

cl-permutation

Source

permutation-generation.lisp (file)

Function: add-generator PERM SGS TRANS K SLP
Package

cl-permutation

Source

permutation-group.lisp (file)

Function: allocate-perm-vector N

Allocate a vector compatible with a size-N permutation.

Package

cl-permutation

Source

permutation.lisp (file)

Function: array-for-spec SPEC &key INITIAL-ELEMENT
Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: assert-valid-permutation-elements ELEMENTS

Verify (via assertions) that the elements

Package

cl-permutation

Source

permutation.lisp (file)

Function: atkinson Ω GS

M. D. Atkinson’s original algorithm as specified in his original paper "An Algorithm for Finding Blocks of a Permutation Group", with very light modifications.

Given a point ω and a list of generators GS, return an array F whose size is max deg(gs), and whose elements are specified as follows:

If a point p appears in F, then the minimal block containing p is the list of all positions of p in F.

Package

cl-permutation

Source

block.lisp (file)

Function: binomial-coefficient-or-zero N K

If N < K, return 0, otherwise return the binomial coefficient.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)

Function: block-slot BLOCK-SUBSYSTEM BLK

In which slot is BLK found in the block subsystem BLOCK-SUBSYSTEM?

Package

cl-permutation

Source

block.lisp (file)

Function: block-subsystem-base-block INSTANCE
Function: (setf block-subsystem-base-block) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: block-subsystem-block-size INSTANCE
Function: (setf block-subsystem-block-size) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: block-subsystem-block-slots INSTANCE
Function: (setf block-subsystem-block-slots) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: block-subsystem-group INSTANCE
Function: (setf block-subsystem-group) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: block-subsystem-orbit INSTANCE
Function: (setf block-subsystem-orbit) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: block-subsystem-p OBJECT
Package

cl-permutation

Source

block.lisp (file)

Function: block-subsystem-size INSTANCE
Function: (setf block-subsystem-size) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: canonicalize-free-group-element G E
Package

cl-permutation

Source

free-group.lisp (file)

Function: canonicalize-raw-block-subsystems BSS

Take a raw list of block systems BSS and canonicalize them.

Package

cl-permutation

Source

block.lisp (file)

Function: check-cycle-elements ELEMENTS

Ensure that the elements ELEMENTS are those of a valid cycle.

Package

cl-permutation

Source

permutation.lisp (file)

Function: clear-membership-set SET
Package

cl-permutation

Source

utilities.lisp (file)

Function: compute-factorization-generators GROUP

Modify the permutation group PERM-GROUP so that it is capable of factorizing elements into generators.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: compute-god-table GROUP &key TARGET VERBOSE
Package

cl-permutation

Source

god.lisp (file)

Function: contains-1-to-n ELEMENTS

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

Package

cl-permutation

Source

permutation.lisp (file)

Function: copy-block-subsystem INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: copy-cycle INSTANCE
Package

cl-permutation

Source

permutation.lisp (file)

Function: copy-djs INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: copy-djs-rep INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: copy-perm INSTANCE
Package

cl-permutation

Source

permutation.lisp (file)

Function: copy-queue INSTANCE
Package

cl-permutation

Source

utilities.lisp (file)

Function: cycle-canonicalized INSTANCE
Function: (setf cycle-canonicalized) VALUE INSTANCE
Package

cl-permutation

Source

permutation.lisp (file)

Function: cycle-p OBJECT
Package

cl-permutation

Source

permutation.lisp (file)

Function: cycle-rep INSTANCE
Function: (setf cycle-rep) VALUE INSTANCE
Package

cl-permutation

Source

permutation.lisp (file)

Function: dequeue QUEUE

Remove and return an element from the queue QUEUE.

Package

cl-permutation

Source

utilities.lisp (file)

Function: djs VALUE

Construct a fresh DJS node.

Package

cl-permutation

Source

block.lisp (file)

Function: djs-change-representative DJS

Change the representative of DJS to point to itself.

Package

cl-permutation

Source

block.lisp (file)

Function: djs-find D

Find the canonical DJS node of which the DJS node D is a part.

Package

cl-permutation

Source

block.lisp (file)

Function: djs-p OBJECT
Package

cl-permutation

Source

block.lisp (file)

Function: djs-rep-djs INSTANCE
Function: (setf djs-rep-djs) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: djs-rep-p OBJECT
Package

cl-permutation

Source

block.lisp (file)

Function: djs-representative INSTANCE
Function: (setf djs-representative) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: djs-union A B

Link together the DJS nodes A and B.

The representative of the union will be that of B.

Package

cl-permutation

Source

block.lisp (file)

Function: djs-value INSTANCE
Function: (setf djs-value) VALUE INSTANCE
Package

cl-permutation

Source

block.lisp (file)

Function: enqueue QUEUE OBJ

Add an element OBJ to the end of the queue QUEUE.

Package

cl-permutation

Source

utilities.lisp (file)

Function: exists-mobile-p PERM LEN
Package

cl-permutation

Source

permutation-generation.lisp (file)

Function: free-group->perm-group-homomorphism FREE-GROUP PERM-GROUP

Construct a homomorphism from the perm group PERM-GROUP’s free group to elements of the perm group itself.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: free-group-element-valid-p G ELEMENT

Given the free group G and some purported element ELEMENT, return a boolean indicating whether it is a valid element of G.

Package

cl-permutation

Source

free-group.lisp (file)

Function: free-group-generator-to-perm-group-generator PERM-GROUP FREE-GROUP-GENERATOR

Convert the free group generator FREE-GROUP-GENERATOR to a generator within the perm group PERM-GROUP.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: generator-exponent-set G

Return a combinatorial specification suitable for searching for subgroups of the group G.

The specification specifies vectors of exponents to the group’s generators, which may be used to generate some subgroups of the group.

Package

cl-permutation

Source

find-subgroups.lisp (file)

Function: generator-orders G

Return the orders of each generator of the group G.

Package

cl-permutation

Source

find-subgroups.lisp (file)

Function: group-block-subsystems GROUP

Return a list of block subsystems of the group GROUP.

Package

cl-permutation

Source

block.lisp (file)

Function: group-bsgs PERM-GROUP

Retrieve a base and associated strong generating set (BSGS) as two values respectively for the permutation group PERM-GROUP.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: group-element-from-signature GROUP SIGNATURE
Package

cl-permutation

Source

do-group-elements.lisp (file)

Function: group-radix GROUP

Compute the radix of the group GROUP.

Package

cl-permutation

Source

do-group-elements.lisp (file)

Function: iota N

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

Package

cl-permutation

Source

utilities.lisp (file)

Function: iota+1 N

Generate a list of numbers between 1 and N.

Package

cl-permutation

Source

utilities.lisp (file)

Function: iota-vector N

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

Package

cl-permutation

Source

utilities.lisp (file)

Function: 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.

Package

cl-permutation

Source

extra-functions.lisp (file)

Function: list-minimum LIST

Find the minimum element of the list via CL:MIN.

Package

cl-permutation

Source

utilities.lisp (file)

Function: list-to-queue LIST

Convert the list LIST into a queue. Note: LIST may be modified.

Package

cl-permutation

Source

utilities.lisp (file)

Function: make-block-subsystem &key (GROUP GROUP) (BASE-BLOCK BASE-BLOCK) (SIZE SIZE) (BLOCK-SIZE BLOCK-SIZE) (ORBIT ORBIT) (BLOCK-SLOTS BLOCK-SLOTS)
Package

cl-permutation

Source

block.lisp (file)

Function: make-membership-set SIZE
Package

cl-permutation

Source

utilities.lisp (file)

Function: make-queue ()

Create a new empty queue.

Package

cl-permutation

Source

utilities.lisp (file)

Function: make-sgs N

Make a strong generating set of size N.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: make-sigma-table K &optional IDENTITY

Make a representation of sigma_K, initialized witk sigma_KK = identity.

The optional argument IDENTITY allows the caller to provide the identity permutation for sigma_kk.

This is represented as an alist mapping J to permutations sigma_KJ.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: make-transversal N

Make a transversal of size N.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: map-cycle-mappings F CYCLE &key OMIT-LAST

Apply a binary function F to all pairs (a_i, b_i) such that the cycle is the composition of a_i |-> b_i.

If OMIT-LAST is T, then the last mapping will be omitted. For example, for the cycle (P1 P2 ... Pn), the mapping Pn |-> P1 will be excluded.

Package

cl-permutation

Source

permutation.lisp (file)

Function: map-exponent-subgroups F GROUP

Map the unary function F across all exponent subgroups of the group GROUP.

Package

cl-permutation

Source

find-subgroups.lisp (file)

Function: map-into-perm FUNCTION PERM-SPEC
Package

cl-permutation

Source

permutation-generation.lisp (file)

Function: map-orbit F N PERM

Given a unary function F, apply it to each element of the orbit of N within the perm PERM.

Package

cl-permutation

Source

permutation.lisp (file)

Function: map-suitable-subgroups F GROUP

Map the unary function F across all suitable subgroups of the group GROUP.

Package

cl-permutation

Source

find-subgroups.lisp (file)

Function: maximum LIST &key KEY

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

Package

cl-permutation

Source

utilities.lisp (file)

Function: membership-set-count SET
Package

cl-permutation

Source

utilities.lisp (file)

Function: membership-set-nunion SET-A SET-B
Package

cl-permutation

Source

utilities.lisp (file)

Function: membership-sets-intersect-p SET-A SET-B
Package

cl-permutation

Source

utilities.lisp (file)

Function: mobilep IDX PERM &optional LEN
Package

cl-permutation

Source

permutation-generation.lisp (file)

Function: next-perm PERM LEN
Package

cl-permutation

Source

permutation-generation.lisp (file)

Function: nshuffle VECTOR &key PARITY START

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

START specifies the starting index where elements should be shuffled.

Package

cl-permutation

Source

utilities.lisp (file)

Function: partition-if F SEQ

Given a predicate F, partition SEQ into two sublists, the first of which has elements that satisfy F, the second which do not.

Package

cl-permutation

Source

utilities.lisp (file)

Function: perm-eject PERM

Remove the largest element of a permutation.

Package

cl-permutation

Source

extra-functions.lisp (file)

Function: perm-extend PERM &optional N

Extend a permutation PERM

Package

cl-permutation

Source

extra-functions.lisp (file)

Function: perm-inject PERM INJECT-TO

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

Package

cl-permutation

Source

extra-functions.lisp (file)

Function: perm-p OBJECT
Package

cl-permutation

Source

permutation.lisp (file)

Function: perm-reader STREAM CHAR N
Package

cl-permutation

Source

permutation.lisp (file)

Function: perm.rep INSTANCE
Function: (setf perm.rep) VALUE INSTANCE
Package

cl-permutation

Source

permutation.lisp (file)

Function: print-cycle CYCLE STREAM DEPTH

Printer for cycles.

An asterisk in printed syntax denotes that the cycle has not been canonicalized (though it may be already be canonical).

Package

cl-permutation

Source

permutation.lisp (file)

Function: print-perm PERM STREAM DEPTH

Printer for perms.

Package

cl-permutation

Source

permutation.lisp (file)

Function: product SEQ &key KEY

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

Package

cl-permutation

Source

utilities.lisp (file)

Function: queue-elements INSTANCE
Function: (setf queue-elements) VALUE INSTANCE
Package

cl-permutation

Source

utilities.lisp (file)

Function: queue-empty-p QUEUE

Is the queue QUEUE empty?

Package

cl-permutation

Source

utilities.lisp (file)

Function: queue-last INSTANCE
Function: (setf queue-last) VALUE INSTANCE
Package

cl-permutation

Source

utilities.lisp (file)

Function: queuep OBJECT
Package

cl-permutation

Source

utilities.lisp (file)

Function: random-between A B

Generate a random integer between A and B, inclusive.

Package

cl-permutation

Source

utilities.lisp (file)

Function: random-element SEQ

Select a random element from the sequence SEQ.

Package

cl-permutation

Source

utilities.lisp (file)

Function: raw-block-subsystems GROUP &key CANONICALIZE

Compute all minimal, disjoint block subsystems of the group GROUP.

Returns a list of block systems.

Package

cl-permutation

Source

block.lisp (file)

Function: reduce-over-trans-decomposition F INITIAL-VALUE PERM TRANS &optional K

Reduce F over the transversal decomposition of PERM within the transversal system TRANS. Return two values:

1. The result of folding over, or NIL if no decomposition exists.
2. NIL iff no decomposition exists.

F is a function of three arguments:

ACCUM: The "accumulator" argument. INITIAL-VALUE is the initial value of this argument.
K, J : Two arguments representing the sigma.

N.B.! The sigma_kj are visited in "right-to-left" compositional order. That is, if S1, S2, ..., Sk are visited sequentially, then PERM is the composition Sk * ... * S2 * S1.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: reverse-direction IDX PERM
Package

cl-permutation

Source

permutation-generation.lisp (file)

Function: rotate-vector! VEC N

Rotate the vector VEC a total of N elements left/counterclockwise in-place. If N is negative, rotate in the opposite direction.

Package

cl-permutation

Source

permutation.lisp (file)

Function: sgs-ref SGS K
Function: (setf sgs-ref) NEW-VALUE SGS K
Package

cl-permutation

Source

permutation-group.lisp (file)

Function: sigma TRANS K J

Retrieve sigma_kj for the transversal system TRANS, or NIL if it doesn’t exist.

Package

cl-permutation

Source

permutation-group.lisp (file)

Writer

(setf sigma) (function)

Function: (setf sigma) NEW-VALUE TRANS K J
Package

cl-permutation

Source

permutation-group.lisp (file)

Reader

sigma (function)

Function: sigma-symbol K J

Return a symbol representing sigma_kj. This is used for perms that are added to the transversal system during group construction.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: sign X

Return the sign of X.

Package

cl-permutation

Source

utilities.lisp (file)

Function: singletonp X

Does X contain one element?

Package

cl-permutation

Source

utilities.lisp (file)

Function: slp-composition%0 INSTANCE
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: slp-composition%1 INSTANCE
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: slp-element%0 INSTANCE
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: slp-inversion%0 INSTANCE
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: slp-symbol%0 INSTANCE
Package

cl-permutation

Source

straight-line-program.lisp (file)

Function: subgroup-from-exponent-vector G V

Generate a subgroup of the group G given the exponent vector V (which was possibly generated by some combinatorial spec, perhaps via #’GENERATOR-EXPONENT-SET).

Package

cl-permutation

Source

find-subgroups.lisp (file)

Function: suitable-subgroup-p G

Is the group G (which is presumably a subgroup of some other group) suitable for further computation?

Package

cl-permutation

Source

find-subgroups.lisp (file)

Function: tau-symbol ()

Return a freshly made symbol for tau.

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: trans-decomposition PERM TRANS &optional K

Decompose PERM into a list of sigmas within the transversal system TRANS. The composition of the sigmas equals the original perm up to K.

The sigma (SIGMA K J) is represented by the cons cell (K . J).

Package

cl-permutation

Source

permutation-group.lisp (file)

Function: trans-element-p PERM TRANS &optional K
Package

cl-permutation

Source

permutation-group.lisp (file)

Function: transversal-ref TRANS K

Get the Kth element of the transversal TRANS. This is representative of all sigma_k.

Package

cl-permutation

Source

permutation-group.lisp (file)

Writer

(setf transversal-ref) (function)

Function: (setf transversal-ref) NEW-VALUE TRANS K
Package

cl-permutation

Source

permutation-group.lisp (file)

Reader

transversal-ref (function)

Function: trivial-block-system-p BS

Is the block system BS a trivial block system?

Package

cl-permutation

Source

block.lisp (file)

Function: update-transversal PERM SGS TRANS K SLP
Package

cl-permutation

Source

permutation-group.lisp (file)

Function: word-generator GROUP
Package

cl-permutation

Source

permutation-group.lisp (file)

Function: word-length W
Package

cl-permutation

Source

permutation-group.lisp (file)

Function: zero-array LENGTH

Make an array of zeroes of length LENGTH.

Package

cl-permutation

Source

combinatorial-ranking.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Generic functions

Generic Function: cardinality-cache OBJECT
Generic Function: (setf cardinality-cache) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: cardinality-cache (COMBINATORIAL-SPEC combinatorial-spec)

automatically generated reader method

Source

combinatorial-ranking.lisp (file)

Method: (setf cardinality-cache) NEW-VALUE (COMBINATORIAL-SPEC combinatorial-spec)

automatically generated writer method

Source

combinatorial-ranking.lisp (file)

Generic Function: comb.zero-count OBJECT
Package

cl-permutation

Methods
Method: comb.zero-count (COMBINATION-SPEC combination-spec)

automatically generated reader method

Source

combinatorial-ranking.lisp (file)

Generic Function: free-group-num-generators OBJECT
Package

cl-permutation

Methods
Method: free-group-num-generators (FREE-GROUP free-group)

automatically generated reader method

Source

free-group.lisp (file)

Generic Function: god-table-generators OBJECT
Package

cl-permutation

Methods
Method: god-table-generators (GOD-TABLE god-table)

automatically generated reader method

Source

god.lisp (file)

Generic Function: god-table-group OBJECT
Package

cl-permutation

Methods
Method: god-table-group (GOD-TABLE god-table)

automatically generated reader method

Source

god.lisp (file)

Generic Function: god-table-target OBJECT
Package

cl-permutation

Methods
Method: god-table-target (GOD-TABLE god-table)

automatically generated reader method

Source

god.lisp (file)

Generic Function: god-table-vector OBJECT
Package

cl-permutation

Methods
Method: god-table-vector (GOD-TABLE god-table)

automatically generated reader method

Source

god.lisp (file)

Generic Function: homomorphism-function OBJECT
Package

cl-permutation

Methods
Method: homomorphism-function (FUNCTION-HOMOMORPHISM function-homomorphism)

Homomorphism function.

Source

homomorphism.lisp (file)

Generic Function: homomorphism-generator-map OBJECT
Package

cl-permutation

Methods
Method: homomorphism-generator-map (GENERATOR-HOMOMORPHISM generator-homomorphism)

A unary function mapping generators of FROM-GROUP to objects of the resulting group TO-GROUP.

Source

homomorphism.lisp (file)

Generic Function: perm-group.element-size OBJECT
Generic Function: (setf perm-group.element-size) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: perm-group.element-size (PERM-GROUP perm-group)
Method: (setf perm-group.element-size) NEW-VALUE (PERM-GROUP perm-group)

The size of the elements of the group. This is a non-negative integer and may be larger than the true degree of the group.

Source

permutation-group.lisp (file)

Generic Function: perm-group.factorization-generators OBJECT
Generic Function: (setf perm-group.factorization-generators) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: perm-group.factorization-generators (PERM-GROUP perm-group)
Method: (setf perm-group.factorization-generators) NEW-VALUE (PERM-GROUP perm-group)

A vector whose length is the same length as the base of the group, whose values are vectors of free-group elements that are coset representatives of the stabilizer G^(i+1)/G^(i). This collection of generators is *also* a strong generating set. This is optionally computed with #’COMPUTE-FACTORIZATION-GENERATORS.

Source

permutation-group.lisp (file)

Generic Function: perm-group.free-group OBJECT
Generic Function: (setf perm-group.free-group) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: perm-group.free-group (PERM-GROUP perm-group)
Method: (setf perm-group.free-group) NEW-VALUE (PERM-GROUP perm-group)

A free group corresponding to the given permutation group.

Source

permutation-group.lisp (file)

Generic Function: perm-group.generators OBJECT
Generic Function: (setf perm-group.generators) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: perm-group.generators (PERM-GROUP perm-group)
Method: (setf perm-group.generators) NEW-VALUE (PERM-GROUP perm-group)

A list of generators of the group.

Source

permutation-group.lisp (file)

Generic Function: perm-group.slp-context OBJECT
Generic Function: (setf perm-group.slp-context) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: perm-group.slp-context (PERM-GROUP perm-group)
Method: (setf perm-group.slp-context) NEW-VALUE (PERM-GROUP perm-group)

SLPs corresponding to all sigmas and strong generators.

Source

permutation-group.lisp (file)

Generic Function: perm-group.strong-generators OBJECT
Generic Function: (setf perm-group.strong-generators) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: perm-group.strong-generators (PERM-GROUP perm-group)
Method: (setf perm-group.strong-generators) NEW-VALUE (PERM-GROUP perm-group)

The strong generating set of the group. This is a vector mapping integers to lists of generators which generate the i’th stabilizer.

Source

permutation-group.lisp (file)

Generic Function: perm-group.transversal-system OBJECT
Generic Function: (setf perm-group.transversal-system) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: perm-group.transversal-system (PERM-GROUP perm-group)
Method: (setf perm-group.transversal-system) NEW-VALUE (PERM-GROUP perm-group)

The transversal system of the group. This is a vector mapping integers K to a table of sigmas SIGMA_K. Every permutation in the group can be represented by a product of permutations SIGMA_K * ... * SIGMA_2 * SIGMA_1.

Source

permutation-group.lisp (file)

Generic Function: reconstruct-perm GOD-TABLE PERM
Package

cl-permutation

Source

god.lisp (file)

Methods
Method: reconstruct-perm (TABLE god-table) PERM
Generic Function: symbol-table OBJECT
Generic Function: (setf symbol-table) NEW-VALUE OBJECT
Package

cl-permutation

Methods
Method: symbol-table (SLP-CONTEXT slp-context)
Method: (setf symbol-table) NEW-VALUE (SLP-CONTEXT slp-context)

A mapping between symbols and their representation as SLPs.

Source

straight-line-program.lisp (file)

Generic Function: word.type-counts OBJECT
Package

cl-permutation

Methods
Method: word.type-counts (WORD-SPEC word-spec)

Vector of non-negative integers representing the count of each individual element type. (The sum of this vector should equal TYPES.)

Source

combinatorial-ranking.lisp (file)

Generic Function: word.types OBJECT
Package

cl-permutation

Methods
Method: word.types (WORD-SPEC word-spec)

Non-negative integer representing the number of distinct elements within the word. Note that this will include the additional zero type, even though there are never any zero elements.

Source

combinatorial-ranking.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.4 Structures

Structure: block-subsystem ()

Representation of a block subsystem of a group. A "block subsystem" is a G-orbit of a block.

Package

cl-permutation

Source

block.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: group
Readers

block-subsystem-group (function)

Writers

(setf block-subsystem-group) (function)

Slot: base-block
Readers

block-subsystem-base-block (function)

Writers

(setf block-subsystem-base-block) (function)

Slot: size
Readers

block-subsystem-size (function)

Writers

(setf block-subsystem-size) (function)

Slot: block-size
Readers

block-subsystem-block-size (function)

Writers

(setf block-subsystem-block-size) (function)

Slot: orbit
Readers

block-subsystem-orbit (function)

Writers

(setf block-subsystem-orbit) (function)

Slot: block-slots
Readers

block-subsystem-block-slots (function)

Writers

(setf block-subsystem-block-slots) (function)

Structure: djs ()

Representation of a disjoint-set data structure. Each node has a representative element denoted by REPRESENTATIVE, which points to a DJS-REP node representing the canonical element of that disjoint-set.

Package

cl-permutation

Source

block.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: representative
Type

(or null cl-permutation::djs-rep)

Readers

djs-representative (function)

Writers

(setf djs-representative) (function)

Slot: value
Readers

djs-value (function)

Writers

(setf djs-value) (function)

Structure: djs-rep ()

Pointer to the representative element of a DJS.

Package

cl-permutation

Source

block.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: djs
Type

cl-permutation::djs

Readers

djs-rep-djs (function)

Writers

(setf djs-rep-djs) (function)

Structure: queue ()
Package

cl-permutation

Source

utilities.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: elements
Type

list

Readers

queue-elements (function)

Writers

(setf queue-elements) (function)

Slot: last
Type

(or null (cons t null))

Readers

queue-last (function)

Writers

(setf queue-last) (function)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.5 Classes

Class: god-table ()
Package

cl-permutation

Source

god.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: group
Initargs

:group

Readers

god-table-group (generic function)

Slot: table
Initargs

:table

Readers

god-table-vector (generic function)

Slot: target
Initargs

:target

Readers

god-table-target (generic function)

Slot: generators
Initargs

:generators

Readers

god-table-generators (generic function)

Class: homomorphism ()
Package

cl-permutation

Source

homomorphism.lisp (file)

Direct superclasses

funcallable-standard-object (class)

Direct subclasses
Direct methods

initialize-instance (method)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.6 Types

Type: raw-perm ()

Type defining the internal representation of a perm.

Package

cl-permutation

Source

permutation.lisp (file)

Type: sgs ()
Package

cl-permutation

Source

permutation-group.lisp (file)

Type: transversal ()
Package

cl-permutation

Source

permutation-group.lisp (file)

Type: vector-index ()

Possible indexes to a vector.

Package

cl-permutation

Source

utilities.lisp (file)

Type: vector-size &key DOWN-BY

Possible sizes of a vector.

Package

cl-permutation

Source

utilities.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   C   F   L  
Index Entry  Section

C
cl-permutation.asd: The cl-permutation<dot>asd file
cl-permutation/block.lisp: The cl-permutation/block<dot>lisp file
cl-permutation/bruhat.lisp: The cl-permutation/bruhat<dot>lisp file
cl-permutation/combinatorial-ranking.lisp: The cl-permutation/combinatorial-ranking<dot>lisp file
cl-permutation/do-group-elements.lisp: The cl-permutation/do-group-elements<dot>lisp file
cl-permutation/extra-functions.lisp: The cl-permutation/extra-functions<dot>lisp file
cl-permutation/find-subgroups.lisp: The cl-permutation/find-subgroups<dot>lisp file
cl-permutation/free-group.lisp: The cl-permutation/free-group<dot>lisp file
cl-permutation/god.lisp: The cl-permutation/god<dot>lisp file
cl-permutation/group.lisp: The cl-permutation/group<dot>lisp file
cl-permutation/homomorphism.lisp: The cl-permutation/homomorphism<dot>lisp file
cl-permutation/orbit.lisp: The cl-permutation/orbit<dot>lisp file
cl-permutation/package.lisp: The cl-permutation/package<dot>lisp file
cl-permutation/permutation-generation.lisp: The cl-permutation/permutation-generation<dot>lisp file
cl-permutation/permutation-group.lisp: The cl-permutation/permutation-group<dot>lisp file
cl-permutation/permutation.lisp: The cl-permutation/permutation<dot>lisp file
cl-permutation/straight-line-program.lisp: The cl-permutation/straight-line-program<dot>lisp file
cl-permutation/utilities.lisp: The cl-permutation/utilities<dot>lisp file

F
File, Lisp, cl-permutation.asd: The cl-permutation<dot>asd file
File, Lisp, cl-permutation/block.lisp: The cl-permutation/block<dot>lisp file
File, Lisp, cl-permutation/bruhat.lisp: The cl-permutation/bruhat<dot>lisp file
File, Lisp, cl-permutation/combinatorial-ranking.lisp: The cl-permutation/combinatorial-ranking<dot>lisp file
File, Lisp, cl-permutation/do-group-elements.lisp: The cl-permutation/do-group-elements<dot>lisp file
File, Lisp, cl-permutation/extra-functions.lisp: The cl-permutation/extra-functions<dot>lisp file
File, Lisp, cl-permutation/find-subgroups.lisp: The cl-permutation/find-subgroups<dot>lisp file
File, Lisp, cl-permutation/free-group.lisp: The cl-permutation/free-group<dot>lisp file
File, Lisp, cl-permutation/god.lisp: The cl-permutation/god<dot>lisp file
File, Lisp, cl-permutation/group.lisp: The cl-permutation/group<dot>lisp file
File, Lisp, cl-permutation/homomorphism.lisp: The cl-permutation/homomorphism<dot>lisp file
File, Lisp, cl-permutation/orbit.lisp: The cl-permutation/orbit<dot>lisp file
File, Lisp, cl-permutation/package.lisp: The cl-permutation/package<dot>lisp file
File, Lisp, cl-permutation/permutation-generation.lisp: The cl-permutation/permutation-generation<dot>lisp file
File, Lisp, cl-permutation/permutation-group.lisp: The cl-permutation/permutation-group<dot>lisp file
File, Lisp, cl-permutation/permutation.lisp: The cl-permutation/permutation<dot>lisp file
File, Lisp, cl-permutation/straight-line-program.lisp: The cl-permutation/straight-line-program<dot>lisp file
File, Lisp, cl-permutation/utilities.lisp: The cl-permutation/utilities<dot>lisp file

L
Lisp File, cl-permutation.asd: The cl-permutation<dot>asd file
Lisp File, cl-permutation/block.lisp: The cl-permutation/block<dot>lisp file
Lisp File, cl-permutation/bruhat.lisp: The cl-permutation/bruhat<dot>lisp file
Lisp File, cl-permutation/combinatorial-ranking.lisp: The cl-permutation/combinatorial-ranking<dot>lisp file
Lisp File, cl-permutation/do-group-elements.lisp: The cl-permutation/do-group-elements<dot>lisp file
Lisp File, cl-permutation/extra-functions.lisp: The cl-permutation/extra-functions<dot>lisp file
Lisp File, cl-permutation/find-subgroups.lisp: The cl-permutation/find-subgroups<dot>lisp file
Lisp File, cl-permutation/free-group.lisp: The cl-permutation/free-group<dot>lisp file
Lisp File, cl-permutation/god.lisp: The cl-permutation/god<dot>lisp file
Lisp File, cl-permutation/group.lisp: The cl-permutation/group<dot>lisp file
Lisp File, cl-permutation/homomorphism.lisp: The cl-permutation/homomorphism<dot>lisp file
Lisp File, cl-permutation/orbit.lisp: The cl-permutation/orbit<dot>lisp file
Lisp File, cl-permutation/package.lisp: The cl-permutation/package<dot>lisp file
Lisp File, cl-permutation/permutation-generation.lisp: The cl-permutation/permutation-generation<dot>lisp file
Lisp File, cl-permutation/permutation-group.lisp: The cl-permutation/permutation-group<dot>lisp file
Lisp File, cl-permutation/permutation.lisp: The cl-permutation/permutation<dot>lisp file
Lisp File, cl-permutation/straight-line-program.lisp: The cl-permutation/straight-line-program<dot>lisp file
Lisp File, cl-permutation/utilities.lisp: The cl-permutation/utilities<dot>lisp file

Jump to:   C   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   %   (  
A   B   C   D   E   F   G   H   I   L   M   N   O   P   Q   R   S   T   U   V   W   Z  
Index Entry  Section

%
%compute-factorization-generators: Internal functions
%make-cycle: Internal functions
%make-djs: Internal functions
%make-djs-rep: Internal functions
%make-perm: Internal functions
%make-queue: Internal functions
%perm-compose-upto: Internal functions

(
(setf block-subsystem-base-block): Internal functions
(setf block-subsystem-block-size): Internal functions
(setf block-subsystem-block-slots): Internal functions
(setf block-subsystem-group): Internal functions
(setf block-subsystem-orbit): Internal functions
(setf block-subsystem-size): Internal functions
(setf cardinality-cache): Internal generic functions
(setf cardinality-cache): Internal generic functions
(setf cycle-canonicalized): Internal functions
(setf cycle-rep): Internal functions
(setf djs-rep-djs): Internal functions
(setf djs-representative): Internal functions
(setf djs-value): Internal functions
(setf perm-group.element-size): Internal generic functions
(setf perm-group.element-size): Internal generic functions
(setf perm-group.factorization-generators): Internal generic functions
(setf perm-group.factorization-generators): Internal generic functions
(setf perm-group.free-group): Internal generic functions
(setf perm-group.free-group): Internal generic functions
(setf perm-group.generators): Internal generic functions
(setf perm-group.generators): Internal generic functions
(setf perm-group.slp-context): Internal generic functions
(setf perm-group.slp-context): Internal generic functions
(setf perm-group.strong-generators): Internal generic functions
(setf perm-group.strong-generators): Internal generic functions
(setf perm-group.transversal-system): Internal generic functions
(setf perm-group.transversal-system): Internal generic functions
(setf perm.rep): Internal functions
(setf queue-elements): Internal functions
(setf queue-last): Internal functions
(setf sgs-ref): Internal functions
(setf sigma): Internal functions
(setf symbol-assignment): Exported functions
(setf symbol-table): Internal generic functions
(setf symbol-table): Internal generic functions
(setf transversal-ref): Internal functions

A
abs>: Internal functions
add-generator: Internal functions
allocate-perm-vector: Internal functions
array-for-spec: Internal functions
assert-valid-permutation-elements: Internal functions
atkinson: Internal functions

B
binomial-coefficient-or-zero: Internal functions
block-slot: Internal functions
block-subsystem-base-block: Internal functions
block-subsystem-block-size: Internal functions
block-subsystem-block-slots: Internal functions
block-subsystem-group: Internal functions
block-subsystem-orbit: Internal functions
block-subsystem-p: Internal functions
block-subsystem-size: Internal functions
bruhat<: Exported functions
bruhat<=: Exported functions

C
canonicalize-cycle: Exported functions
canonicalize-cycles: Exported functions
canonicalize-free-group-element: Internal functions
canonicalize-raw-block-subsystems: Internal functions
cardinality: Exported generic functions
cardinality: Exported generic functions
cardinality: Exported generic functions
cardinality: Exported generic functions
cardinality: Exported generic functions
cardinality: Exported generic functions
cardinality: Exported generic functions
cardinality-cache: Internal generic functions
cardinality-cache: Internal generic functions
check-cycle-elements: Internal functions
clear-membership-set: Internal functions
comb.zero-count: Internal generic functions
comb.zero-count: Internal generic functions
compose: Exported generic functions
compose: Exported generic functions
compose: Exported generic functions
compose-slp: Exported functions
compute-factorization-generators: Internal functions
compute-god-table: Internal functions
contains-1-to-n: Internal functions
copy-block-subsystem: Internal functions
copy-cycle: Internal functions
copy-djs: Internal functions
copy-djs-rep: Internal functions
copy-perm: Internal functions
copy-queue: Internal functions
cycle-canonicalized: Internal functions
cycle-identity-p: Exported functions
cycle-length: Exported functions
cycle-p: Internal functions
cycle-ref: Exported functions
cycle-rep: Internal functions
cycle-type: Exported functions
cycles-to-one-line: Exported functions

D
dequeue: Internal functions
djs: Internal functions
djs-change-representative: Internal functions
djs-find: Internal functions
djs-p: Internal functions
djs-rep-djs: Internal functions
djs-rep-p: Internal functions
djs-representative: Internal functions
djs-union: Internal functions
djs-value: Internal functions
do-group-elements: Exported macros
doperms: Exported macros

E
enable-perm-reader: Exported functions
enqueue: Internal functions
evaluate-slp: Exported functions
exists-mobile-p: Internal functions

F
find-conjugator: Exported functions
find-minimal-block-system-containing: Exported functions
find-non-trivial-block-system: Exported functions
free-group->perm-group-homomorphism: Internal functions
free-group-element-valid-p: Internal functions
free-group-generator-to-perm-group-generator: Internal functions
free-group-identity-p: Exported functions
free-group-num-generators: Internal generic functions
free-group-num-generators: Internal generic functions
from-cycles: Exported functions
Function, %compute-factorization-generators: Internal functions
Function, %make-cycle: Internal functions
Function, %make-djs: Internal functions
Function, %make-djs-rep: Internal functions
Function, %make-perm: Internal functions
Function, %make-queue: Internal functions
Function, %perm-compose-upto: Internal functions
Function, (setf block-subsystem-base-block): Internal functions
Function, (setf block-subsystem-block-size): Internal functions
Function, (setf block-subsystem-block-slots): Internal functions
Function, (setf block-subsystem-group): Internal functions
Function, (setf block-subsystem-orbit): Internal functions
Function, (setf block-subsystem-size): Internal functions
Function, (setf cycle-canonicalized): Internal functions
Function, (setf cycle-rep): Internal functions
Function, (setf djs-rep-djs): Internal functions
Function, (setf djs-representative): Internal functions
Function, (setf djs-value): Internal functions
Function, (setf perm.rep): Internal functions
Function, (setf queue-elements): Internal functions
Function, (setf queue-last): Internal functions
Function, (setf sgs-ref): Internal functions
Function, (setf sigma): Internal functions
Function, (setf symbol-assignment): Exported functions
Function, (setf transversal-ref): Internal functions
Function, abs>: Internal functions
Function, add-generator: Internal functions
Function, allocate-perm-vector: Internal functions
Function, array-for-spec: Internal functions
Function, assert-valid-permutation-elements: Internal functions
Function, atkinson: Internal functions
Function, binomial-coefficient-or-zero: Internal functions
Function, block-slot: Internal functions
Function, block-subsystem-base-block: Internal functions
Function, block-subsystem-block-size: Internal functions
Function, block-subsystem-block-slots: Internal functions
Function, block-subsystem-group: Internal functions
Function, block-subsystem-orbit: Internal functions
Function, block-subsystem-p: Internal functions
Function, block-subsystem-size: Internal functions
Function, bruhat<: Exported functions
Function, bruhat<=: Exported functions
Function, canonicalize-cycle: Exported functions
Function, canonicalize-cycles: Exported functions
Function, canonicalize-free-group-element: Internal functions
Function, canonicalize-raw-block-subsystems: Internal functions
Function, check-cycle-elements: Internal functions
Function, clear-membership-set: Internal functions
Function, compose-slp: Exported functions
Function, compute-factorization-generators: Internal functions
Function, compute-god-table: Internal functions
Function, contains-1-to-n: Internal functions
Function, copy-block-subsystem: Internal functions
Function, copy-cycle: Internal functions
Function, copy-djs: Internal functions
Function, copy-djs-rep: Internal functions
Function, copy-perm: Internal functions
Function, copy-queue: Internal functions
Function, cycle-canonicalized: Internal functions
Function, cycle-identity-p: Exported functions
Function, cycle-length: Exported functions
Function, cycle-p: Internal functions
Function, cycle-ref: Exported functions
Function, cycle-rep: Internal functions
Function, cycle-type: Exported functions
Function, cycles-to-one-line: Exported functions
Function, dequeue: Internal functions
Function, djs: Internal functions
Function, djs-change-representative: Internal functions
Function, djs-find: Internal functions
Function, djs-p: Internal functions
Function, djs-rep-djs: Internal functions
Function, djs-rep-p: Internal functions
Function, djs-representative: Internal functions
Function, djs-union: Internal functions
Function, djs-value: Internal functions
Function, enable-perm-reader: Exported functions
Function, enqueue: Internal functions
Function, evaluate-slp: Exported functions
Function, exists-mobile-p: Internal functions
Function, find-conjugator: Exported functions
Function, find-minimal-block-system-containing: Exported functions
Function, find-non-trivial-block-system: Exported functions
Function, free-group->perm-group-homomorphism: Internal functions
Function, free-group-element-valid-p: Internal functions
Function, free-group-generator-to-perm-group-generator: Internal functions
Function, free-group-identity-p: Exported functions
Function, from-cycles: Exported functions
Function, generate-perm-group: Exported functions
Function, generator-decomposition: Exported functions
Function, generator-exponent-set: Internal functions
Function, generator-orders: Internal functions
Function, group-block-subsystems: Internal functions
Function, group-bsgs: Internal functions
Function, group-degree: Exported functions
Function, group-element-from-signature: Internal functions
Function, group-element-p: Exported functions
Function, group-element-rank-functions: Exported functions
Function, group-from: Exported functions
Function, group-from-cycles: Exported functions
Function, group-from-orbit: Exported functions
Function, group-identity: Exported functions
Function, group-orbits: Exported functions
Function, group-order: Exported functions
Function, group-radix: Internal functions
Function, homomorphism-induced-perm-group: Exported functions
Function, invert-slp: Exported functions
Function, iota: Internal functions
Function, iota+1: Internal functions
Function, iota-vector: Internal functions
Function, last-to-position: Internal functions
Function, list-minimum: Internal functions
Function, list-to-perm: Exported functions
Function, list-to-queue: Internal functions
Function, make-block-subsystem: Internal functions
Function, make-combination-spec: Exported functions
Function, make-cycle: Exported functions
Function, make-free-group: Exported functions
Function, make-free-group-element: Exported functions
Function, make-membership-set: Internal functions
Function, make-perm: Exported functions
Function, make-perm-generator: Exported functions
Function, make-perm-spec: Exported functions
Function, make-queue: Internal functions
Function, make-radix-spec: Exported functions
Function, make-sgs: Internal functions
Function, make-sigma-table: Internal functions
Function, make-transversal: Internal functions
Function, map-cycle-mappings: Internal functions
Function, map-exponent-subgroups: Internal functions
Function, map-into-perm: Internal functions
Function, map-orbit: Internal functions
Function, map-spec: Exported functions
Function, map-suitable-subgroups: Internal functions
Function, maximum: Internal functions
Function, membership-set-count: Internal functions
Function, membership-set-nunion: Internal functions
Function, membership-sets-intersect-p: Internal functions
Function, mobilep: Internal functions
Function, naive-generator-decomposition: Exported functions
Function, next-perm: Internal functions
Function, nshuffle: Internal functions
Function, orbit-group-homomorphism: Exported functions
Function, orbit-length: Exported functions
Function, orbit-of: Exported functions
Function, partition-if: Internal functions
Function, perm-compose: Exported functions
Function, perm-compose-flipped: Exported functions
Function, perm-conjugate: Exported functions
Function, perm-eject: Internal functions
Function, perm-eval: Exported functions
Function, perm-eval*: Exported functions
Function, perm-evaluator: Exported functions
Function, perm-evaluator*: Exported functions
Function, perm-even-p: Exported functions
Function, perm-expt: Exported functions
Function, perm-extend: Internal functions
Function, perm-fixpoints: Exported functions
Function, perm-identity: Exported functions
Function, perm-identity-p: Exported functions
Function, perm-inject: Internal functions
Function, perm-inverse: Exported functions
Function, perm-inverse-eval: Exported functions
Function, perm-inverse-eval*: Exported functions
Function, perm-last-non-fixpoint: Exported functions
Function, perm-length: Exported functions
Function, perm-odd-p: Exported functions
Function, perm-order: Exported functions
Function, perm-p: Internal functions
Function, perm-point-fixed-p: Exported functions
Function, perm-reader: Internal functions
Function, perm-ref: Exported functions
Function, perm-sign: Exported functions
Function, perm-size: Exported functions
Function, perm-to-list: Exported functions
Function, perm-to-vector: Exported functions
Function, perm-transpose-entries: Exported functions
Function, perm-transpose-indexes: Exported functions
Function, perm.rep: Internal functions
Function, perm=: Exported functions
Function, perm=*: Exported functions
Function, permute: Exported functions
Function, primitive-group-p: Exported functions
Function, print-cycle: Internal functions
Function, print-objects-of-spec: Exported functions
Function, print-perm: Internal functions
Function, product: Internal functions
Function, queue-elements: Internal functions
Function, queue-empty-p: Internal functions
Function, queue-last: Internal functions
Function, queuep: Internal functions
Function, random-between: Internal functions
Function, random-element: Internal functions
Function, random-group-element: Exported functions
Function, random-perm: Exported functions
Function, raw-block-subsystems: Internal functions
Function, reduce-over-trans-decomposition: Internal functions
Function, reverse-direction: Internal functions
Function, rotate-cycle: Exported functions
Function, rotate-vector!: Internal functions
Function, sgs-ref: Internal functions
Function, sigma: Internal functions
Function, sigma-symbol: Internal functions
Function, sign: Internal functions
Function, singletonp: Internal functions
Function, slp-composition: Exported functions
Function, slp-composition%0: Internal functions
Function, slp-composition%1: Internal functions
Function, slp-element: Exported functions
Function, slp-element%0: Internal functions
Function, slp-inversion: Exported functions
Function, slp-inversion%0: Internal functions
Function, slp-symbol: Exported functions
Function, slp-symbol%0: Internal functions
Function, subdirect-factors: Exported functions
Function, subgroup-from-exponent-vector: Internal functions
Function, subgroup-p: Exported functions
Function, suitable-subgroup-p: Internal functions
Function, symbol-assignment: Exported functions
Function, tau-symbol: Internal functions
Function, to-cycles: Exported functions
Function, trans-decomposition: Internal functions
Function, trans-element-p: Internal functions
Function, transversal-decomposition: Exported functions
Function, transversal-ref: Internal functions
Function, trivial-block-system-p: Internal functions
Function, update-transversal: Internal functions
Function, vector-to-mixed-radix-spec: Exported functions
Function, vector-to-perm: Exported functions
Function, vector-to-word-spec: Exported functions
Function, word-generator: Internal functions
Function, word-length: Internal functions
Function, zero-array: Internal functions

G
generate-perm-group: Exported functions
generator-decomposition: Exported functions
generator-exponent-set: Internal functions
generator-orders: Internal functions
generators: Exported generic functions
generators: Exported generic functions
generators: Exported generic functions
Generic Function, (setf cardinality-cache): Internal generic functions
Generic Function, (setf perm-group.element-size): Internal generic functions
Generic Function, (setf perm-group.factorization-generators): Internal generic functions
Generic Function, (setf perm-group.free-group): Internal generic functions
Generic Function, (setf perm-group.generators): Internal generic functions
Generic Function, (setf perm-group.slp-context): Internal generic functions
Generic Function, (setf perm-group.strong-generators): Internal generic functions
Generic Function, (setf perm-group.transversal-system): Internal generic functions
Generic Function, (setf symbol-table): Internal generic functions
Generic Function, cardinality: Exported generic functions
Generic Function, cardinality-cache: Internal generic functions
Generic Function, comb.zero-count: Internal generic functions
Generic Function, compose: Exported generic functions
Generic Function, free-group-num-generators: Internal generic functions
Generic Function, generators: Exported generic functions
Generic Function, god-table-generators: Internal generic functions
Generic Function, god-table-group: Internal generic functions
Generic Function, god-table-target: Internal generic functions
Generic Function, god-table-vector: Internal generic functions
Generic Function, homomorphism-function: Internal generic functions
Generic Function, homomorphism-generator-map: Internal generic functions
Generic Function, homomorphism-image: Exported generic functions
Generic Function, homomorphism-preimage: Exported generic functions
Generic Function, identity-element: Exported generic functions
Generic Function, image: Exported generic functions
Generic Function, inverse: Exported generic functions
Generic Function, num-generators: Exported generic functions
Generic Function, perm-group.element-size: Internal generic functions
Generic Function, perm-group.factorization-generators: Internal generic functions
Generic Function, perm-group.free-group: Internal generic functions
Generic Function, perm-group.generators: Internal generic functions
Generic Function, perm-group.slp-context: Internal generic functions
Generic Function, perm-group.strong-generators: Internal generic functions
Generic Function, perm-group.transversal-system: Internal generic functions
Generic Function, radix: Exported generic functions
Generic Function, rank: Exported generic functions
Generic Function, reconstruct-perm: Internal generic functions
Generic Function, size: Exported generic functions
Generic Function, symbol-table: Internal generic functions
Generic Function, unrank: Exported generic functions
Generic Function, word.type-counts: Internal generic functions
Generic Function, word.types: Internal generic functions
god-table-generators: Internal generic functions
god-table-generators: Internal generic functions
god-table-group: Internal generic functions
god-table-group: Internal generic functions
god-table-target: Internal generic functions
god-table-target: Internal generic functions
god-table-vector: Internal generic functions
god-table-vector: Internal generic functions
group-block-subsystems: Internal functions
group-bsgs: Internal functions
group-degree: Exported functions
group-element-from-signature: Internal functions
group-element-p: Exported functions
group-element-rank-functions: Exported functions
group-from: Exported functions
group-from-cycles: Exported functions
group-from-orbit: Exported functions
group-identity: Exported functions
group-orbits: Exported functions
group-order: Exported functions
group-radix: Internal functions

H
homomorphism-function: Internal generic functions
homomorphism-function: Internal generic functions
homomorphism-generator-map: Internal generic functions
homomorphism-generator-map: Internal generic functions
homomorphism-image: Exported generic functions
homomorphism-image: Exported generic functions
homomorphism-image: Exported generic functions
homomorphism-induced-perm-group: Exported functions
homomorphism-preimage: Exported generic functions
homomorphism-preimage: Exported generic functions
homomorphism-preimage: Exported generic functions

I
identity-element: Exported generic functions
identity-element: Exported generic functions
identity-element: Exported generic functions
image: Exported generic functions
image: Exported generic functions
image: Exported generic functions
image: Exported generic functions
inverse: Exported generic functions
inverse: Exported generic functions
inverse: Exported generic functions
invert-slp: Exported functions
iota: Internal functions
iota+1: Internal functions
iota-vector: Internal functions

L
last-to-position: Internal functions
list-minimum: Internal functions
list-to-perm: Exported functions
list-to-queue: Internal functions

M
Macro, do-group-elements: Exported macros
Macro, doperms: Exported macros
make-block-subsystem: Internal functions
make-combination-spec: Exported functions
make-cycle: Exported functions
make-free-group: Exported functions
make-free-group-element: Exported functions
make-membership-set: Internal functions
make-perm: Exported functions
make-perm-generator: Exported functions
make-perm-spec: Exported functions
make-queue: Internal functions
make-radix-spec: Exported functions
make-sgs: Internal functions
make-sigma-table: Internal functions
make-transversal: Internal functions
map-cycle-mappings: Internal functions
map-exponent-subgroups: Internal functions
map-into-perm: Internal functions
map-orbit: Internal functions
map-spec: Exported functions
map-suitable-subgroups: Internal functions
maximum: Internal functions
membership-set-count: Internal functions
membership-set-nunion: Internal functions
membership-sets-intersect-p: Internal functions
Method, (setf cardinality-cache): Internal generic functions
Method, (setf perm-group.element-size): Internal generic functions
Method, (setf perm-group.factorization-generators): Internal generic functions
Method, (setf perm-group.free-group): Internal generic functions
Method, (setf perm-group.generators): Internal generic functions
Method, (setf perm-group.slp-context): Internal generic functions
Method, (setf perm-group.strong-generators): Internal generic functions
Method, (setf perm-group.transversal-system): Internal generic functions
Method, (setf symbol-table): Internal generic functions
Method, cardinality: Exported generic functions
Method, cardinality: Exported generic functions
Method, cardinality: Exported generic functions
Method, cardinality: Exported generic functions
Method, cardinality: Exported generic functions
Method, cardinality: Exported generic functions
Method, cardinality-cache: Internal generic functions
Method, comb.zero-count: Internal generic functions
Method, compose: Exported generic functions
Method, compose: Exported generic functions
Method, free-group-num-generators: Internal generic functions
Method, generators: Exported generic functions
Method, generators: Exported generic functions
Method, god-table-generators: Internal generic functions
Method, god-table-group: Internal generic functions
Method, god-table-target: Internal generic functions
Method, god-table-vector: Internal generic functions
Method, homomorphism-function: Internal generic functions
Method, homomorphism-generator-map: Internal generic functions
Method, homomorphism-image: Exported generic functions
Method, homomorphism-image: Exported generic functions
Method, homomorphism-preimage: Exported generic functions
Method, homomorphism-preimage: Exported generic functions
Method, identity-element: Exported generic functions
Method, identity-element: Exported generic functions
Method, image: Exported generic functions
Method, image: Exported generic functions
Method, image: Exported generic functions
Method, inverse: Exported generic functions
Method, inverse: Exported generic functions
Method, num-generators: Exported generic functions
Method, num-generators: Exported generic functions
Method, perm-group.element-size: Internal generic functions
Method, perm-group.factorization-generators: Internal generic functions
Method, perm-group.free-group: Internal generic functions
Method, perm-group.generators: Internal generic functions
Method, perm-group.slp-context: Internal generic functions
Method, perm-group.strong-generators: Internal generic functions
Method, perm-group.transversal-system: Internal generic functions
Method, radix: Exported generic functions
Method, radix: Exported generic functions
Method, rank: Exported generic functions
Method, rank: Exported generic functions
Method, rank: Exported generic functions
Method, rank: Exported generic functions
Method, rank: Exported generic functions
Method, reconstruct-perm: Internal generic functions
Method, size: Exported generic functions
Method, symbol-table: Internal generic functions
Method, unrank: Exported generic functions
Method, unrank: Exported generic functions
Method, unrank: Exported generic functions
Method, unrank: Exported generic functions
Method, unrank: Exported generic functions
Method, word.type-counts: Internal generic functions
Method, word.types: Internal generic functions
mobilep: Internal functions

N
naive-generator-decomposition: Exported functions
next-perm: Internal functions
nshuffle: Internal functions
num-generators: Exported generic functions
num-generators: Exported generic functions
num-generators: Exported generic functions

O
orbit-group-homomorphism: Exported functions
orbit-length: Exported functions
orbit-of: Exported functions

P
partition-if: Internal functions
perm-compose: Exported functions
perm-compose-flipped: Exported functions
perm-conjugate: Exported functions
perm-eject: Internal functions
perm-eval: Exported functions
perm-eval*: Exported functions
perm-evaluator: Exported functions
perm-evaluator*: Exported functions
perm-even-p: Exported functions
perm-expt: Exported functions
perm-extend: Internal functions
perm-fixpoints: Exported functions
perm-group.element-size: Internal generic functions
perm-group.element-size: Internal generic functions
perm-group.factorization-generators: Internal generic functions
perm-group.factorization-generators: Internal generic functions
perm-group.free-group: Internal generic functions
perm-group.free-group: Internal generic functions
perm-group.generators: Internal generic functions
perm-group.generators: Internal generic functions
perm-group.slp-context: Internal generic functions
perm-group.slp-context: Internal generic functions
perm-group.strong-generators: Internal generic functions
perm-group.strong-generators: Internal generic functions
perm-group.transversal-system: Internal generic functions
perm-group.transversal-system: Internal generic functions
perm-identity: Exported functions
perm-identity-p: Exported functions
perm-inject: Internal functions
perm-inverse: Exported functions
perm-inverse-eval: Exported functions
perm-inverse-eval*: Exported functions
perm-last-non-fixpoint: Exported functions
perm-length: Exported functions
perm-odd-p: Exported functions
perm-order: Exported functions
perm-p: Internal functions
perm-point-fixed-p: Exported functions
perm-reader: Internal functions
perm-ref: Exported functions
perm-sign: Exported functions
perm-size: Exported functions
perm-to-list: Exported functions
perm-to-vector: Exported functions
perm-transpose-entries: Exported functions
perm-transpose-indexes: Exported functions
perm.rep: Internal functions
perm=: Exported functions
perm=*: Exported functions
permute: Exported functions
primitive-group-p: Exported functions
print-cycle: Internal functions
print-objects-of-spec: Exported functions
print-perm: Internal functions
product: Internal functions

Q
queue-elements: Internal functions
queue-empty-p: Internal functions
queue-last: Internal functions
queuep: Internal functions

R
radix: Exported generic functions
radix: Exported generic functions
radix: Exported generic functions
random-between: Internal functions
random-element: Internal functions
random-group-element: Exported functions
random-perm: Exported functions
rank: Exported generic functions
rank: Exported generic functions
rank: Exported generic functions
rank: Exported generic functions
rank: Exported generic functions
rank: Exported generic functions
raw-block-subsystems: Internal functions
reconstruct-perm: Internal generic functions
reconstruct-perm: Internal generic functions
reduce-over-trans-decomposition: Internal functions
reverse-direction: Internal functions
rotate-cycle: Exported functions
rotate-vector!: Internal functions

S
sgs-ref: Internal functions
sigma: Internal functions
sigma-symbol: Internal functions
sign: Internal functions
singletonp: Internal functions
size: Exported generic functions
size: Exported generic functions
slp-composition: Exported functions
slp-composition%0: Internal functions
slp-composition%1: Internal functions
slp-element: Exported functions
slp-element%0: Internal functions
slp-inversion: Exported functions
slp-inversion%0: Internal functions
slp-symbol: Exported functions
slp-symbol%0: Internal functions
subdirect-factors: Exported functions
subgroup-from-exponent-vector: Internal functions
subgroup-p: Exported functions
suitable-subgroup-p: Internal functions
symbol-assignment: Exported functions
symbol-table: Internal generic functions
symbol-table: Internal generic functions

T
tau-symbol: Internal functions
to-cycles: Exported functions
trans-decomposition: Internal functions
trans-element-p: Internal functions
transversal-decomposition: Exported functions
transversal-ref: Internal functions
trivial-block-system-p: Internal functions

U
unrank: Exported generic functions
unrank: Exported generic functions
unrank: Exported generic functions
unrank: Exported generic functions
unrank: Exported generic functions
unrank: Exported generic functions
update-transversal: Internal functions

V
vector-to-mixed-radix-spec: Exported functions
vector-to-perm: Exported functions
vector-to-word-spec: Exported functions

W
word-generator: Internal functions
word-length: Internal functions
word.type-counts: Internal generic functions
word.type-counts: Internal generic functions
word.types: Internal generic functions
word.types: Internal generic functions

Z
zero-array: Internal functions

Jump to:   %   (  
A   B   C   D   E   F   G   H   I   L   M   N   O   P   Q   R   S   T   U   V   W   Z  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   %   *  
B   C   D   E   F   G   L   N   O   R   S   T   V   Z  
Index Entry  Section

%
%0: Exported structures
%0: Exported structures
%0: Exported structures
%0: Exported structures
%1: Exported structures

*
*canonicalize-cycle-on-creation*: Exported special variables
*context*: Internal special variables
*perm-group-verbose*: Internal special variables
*print-with-perm-syntax*: Internal special variables
*taus*: Internal special variables

B
base-block: Internal structures
block-size: Internal structures
block-slots: Internal structures

C
canonicalized: Exported structures
cardinality-cache: Exported classes

D
djs: Internal structures

E
element-size: Exported classes
elements: Internal structures

F
factorization-generators: Exported classes
free-group: Exported classes
from-group: Exported classes
from-group: Exported classes
function: Exported classes

G
generator-map: Exported classes
generators: Exported classes
generators: Internal classes
group: Internal structures
group: Internal classes

L
last: Internal structures

N
num-generators: Exported classes

O
orbit: Internal structures

R
radix: Exported classes
radix: Exported classes
rep: Exported structures
rep: Exported structures
representative: Internal structures

S
size: Exported classes
size: Internal structures
Slot, %0: Exported structures
Slot, %0: Exported structures
Slot, %0: Exported structures
Slot, %0: Exported structures
Slot, %1: Exported structures
Slot, base-block: Internal structures
Slot, block-size: Internal structures
Slot, block-slots: Internal structures
Slot, canonicalized: Exported structures
Slot, cardinality-cache: Exported classes
Slot, djs: Internal structures
Slot, element-size: Exported classes
Slot, elements: Internal structures
Slot, factorization-generators: Exported classes
Slot, free-group: Exported classes
Slot, from-group: Exported classes
Slot, from-group: Exported classes
Slot, function: Exported classes
Slot, generator-map: Exported classes
Slot, generators: Exported classes
Slot, generators: Internal classes
Slot, group: Internal structures
Slot, group: Internal classes
Slot, last: Internal structures
Slot, num-generators: Exported classes
Slot, orbit: Internal structures
Slot, radix: Exported classes
Slot, radix: Exported classes
Slot, rep: Exported structures
Slot, rep: Exported structures
Slot, representative: Internal structures
Slot, size: Exported classes
Slot, size: Internal structures
Slot, slp-context: Exported classes
Slot, strong-generators: Exported classes
Slot, symbol-table: Exported classes
Slot, table: Internal classes
Slot, target: Internal classes
Slot, to-group: Exported classes
Slot, to-group: Exported classes
Slot, transversal-system: Exported classes
Slot, type-counts: Exported classes
Slot, types: Exported classes
Slot, value: Internal structures
Slot, zero-count: Exported classes
slp-context: Exported classes
Special Variable, *canonicalize-cycle-on-creation*: Exported special variables
Special Variable, *context*: Internal special variables
Special Variable, *perm-group-verbose*: Internal special variables
Special Variable, *print-with-perm-syntax*: Internal special variables
Special Variable, *taus*: Internal special variables
strong-generators: Exported classes
symbol-table: Exported classes

T
table: Internal classes
target: Internal classes
to-group: Exported classes
to-group: Exported classes
transversal-system: Exported classes
type-counts: Exported classes
types: Exported classes

V
value: Internal structures

Z
zero-count: Exported classes

Jump to:   %   *  
B   C   D   E   F   G   L   N   O   R   S   T   V   Z  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   B   C   D   F   G   H   M   P   Q   R   S   T   V   W  
Index Entry  Section

B
block-subsystem: Internal structures

C
cl-permutation: The cl-permutation system
cl-permutation: The cl-permutation package
Class, combination-spec: Exported classes
Class, combinatorial-spec: Exported classes
Class, free-group: Exported classes
Class, function-homomorphism: Exported classes
Class, generator-homomorphism: Exported classes
Class, god-table: Internal classes
Class, homomorphism: Internal classes
Class, mixed-radix-spec: Exported classes
Class, perm-group: Exported classes
Class, perm-spec: Exported classes
Class, radix-spec: Exported classes
Class, slp-context: Exported classes
Class, word-spec: Exported classes
combination-spec: Exported classes
combinatorial-spec: Exported classes
cycle: Exported structures
cycle-element: Exported types

D
djs: Internal structures
djs-rep: Internal structures

F
free-group: Exported classes
function-homomorphism: Exported classes

G
generator-homomorphism: Exported classes
god-table: Internal classes

H
homomorphism: Internal classes

M
mixed-radix-spec: Exported classes

P
Package, cl-permutation: The cl-permutation package
perm: Exported structures
perm-element: Exported types
perm-group: Exported classes
perm-spec: Exported classes

Q
queue: Internal structures

R
radix-spec: Exported classes
raw-perm: Internal types

S
sgs: Internal types
slp: Exported structures
slp-composition: Exported structures
slp-context: Exported classes
slp-element: Exported structures
slp-inversion: Exported structures
slp-symbol: Exported structures
Structure, block-subsystem: Internal structures
Structure, cycle: Exported structures
Structure, djs: Internal structures
Structure, djs-rep: Internal structures
Structure, perm: Exported structures
Structure, queue: Internal structures
Structure, slp: Exported structures
Structure, slp-composition: Exported structures
Structure, slp-element: Exported structures
Structure, slp-inversion: Exported structures
Structure, slp-symbol: Exported structures
System, cl-permutation: The cl-permutation system

T
transversal: Internal types
Type, cycle-element: Exported types
Type, perm-element: Exported types
Type, raw-perm: Internal types
Type, sgs: Internal types
Type, transversal: Internal types
Type, vector-index: Internal types
Type, vector-size: Internal types

V
vector-index: Internal types
vector-size: Internal types

W
word-spec: Exported classes

Jump to:   B   C   D   F   G   H   M   P   Q   R   S   T   V   W