# The cl-permutation Reference Manual

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

# The cl-permutation Reference Manual

This is the cl-permutation Reference Manual, generated automatically by Declt version 2.3 "Robert April" on Wed Mar 14 03:28:46 2018 GMT+0.

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

# 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]
``````

## Permutation Operations

There is a slew of permutation operations:

• `perm-identity`: construct an identity perm
• `perm-identity-p`: check if a perm is an identity perm
• `random-perm`: construct a random perm with specified parity
• `perm-ref`: zero-based reference
• `perm-eval`: one-based (standard) reference
• `perm-eval*`: one-based (standard) reference with out-of-bounds handling
• `perm-inverse-eval`: one-based (standard) reference of inverse
• `perm-inverse-eval*`: one-based (standard) reference of inverse with out-of-bounds handling
• `perm=`: check for equality
• `perm=*`: check for equality of different sized perms
• `perm-size`: the size of the permutation (number of mapped elements)
• `perm-length`: number of inversions
• `perm-even-p`: check for evenness/oddness
• `perm-odd-p`: ''
• `perm-sign`: ''
• `perm-compose`: compose two permutations
• `perm-expt`: compose a perm with itself a number of times
• `perm-order`: order of a permutation
• `perm-transpose-indexes`: swap two indexes, keeping the entries fixed
• `perm-transpose-entries`: swap two entries, keeping the indexes fixed
• `perm-inverse`: invert a permutation
• `perm-fixpoints`: compute the fixed points of a permutation
• `permute`: permute an array according to a permutation

## 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 contain their least element positionally first.
• Cycles are listed in descending order of their first element.
• No null cycles exist.
• The sum of the cycle lengths of a decomposition of a permutation of size `N` is `N`.

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>

Description

A library for operating on permutations and permutation groups.

Dependencies
• alexandria
• iterate
• cl-algebraic-data-type
• closer-mop
• uiop
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/quickbuilder/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

#### 3.1.3 cl-permutation/utilities.lisp

Dependency

package.lisp (file)

Parent

cl-permutation (system)

Location

utilities.lisp

Internal Definitions

#### 3.1.4 cl-permutation/permutation.lisp

Dependency

utilities.lisp (file)

Parent

cl-permutation (system)

Location

permutation.lisp

Exported Definitions
Internal Definitions

#### 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

#### 3.1.7 cl-permutation/group.lisp

Dependency
Parent

cl-permutation (system)

Location

group.lisp

Exported Definitions

#### 3.1.8 cl-permutation/free-group.lisp

Dependency

group.lisp (file)

Parent

cl-permutation (system)

Location

free-group.lisp

Exported Definitions
Internal Definitions

#### 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

#### 3.1.10 cl-permutation/permutation-group.lisp

Dependency
Parent

cl-permutation (system)

Location

permutation-group.lisp

Exported Definitions
Internal Definitions

#### 3.1.11 cl-permutation/homomorphism.lisp

Dependency

permutation-group.lisp (file)

Parent

cl-permutation (system)

Location

homomorphism.lisp

Exported Definitions
Internal Definitions

#### 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

#### 3.1.14 cl-permutation/block.lisp

Dependency

do-group-elements.lisp (file)

Parent

cl-permutation (system)

Location

block.lisp

Exported Definitions
Internal Definitions

#### 3.1.15 cl-permutation/combinatorial-ranking.lisp

Dependency

block.lisp (file)

Parent

cl-permutation (system)

Location

combinatorial-ranking.lisp

Exported Definitions
Internal Definitions

#### 3.1.16 cl-permutation/find-subgroups.lisp

Dependency
Parent

cl-permutation (system)

Location

find-subgroups.lisp

Internal Definitions

#### 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
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
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
Source

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
Source

bruhat.lisp (file)

Function: bruhat<= W V

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

Package
Source

bruhat.lisp (file)

Function: canonicalize-cycle CYCLE

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

Package
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
Source

permutation.lisp (file)

Function: compose-slp SLP1 SLP2

Compose two SLPs SLP1 and SLP2.

Package
Source
Function: cycle-identity-p CYCLE

Is the cycle CYCLE representative of an identity permutation?

Package
Source

permutation.lisp (file)

Function: cycle-length CYCLE

Compute the length of the cycle CYCLE.

Package
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
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
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
Source

permutation.lisp (file)

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

Package
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
Source
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
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
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
Source

block.lisp (file)

Function: free-group-identity-p X

Is X an identity element of a free group?

Package
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
Source

permutation.lisp (file)

Function: generate-perm-group GENERATORS

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

Package
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
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
Source

permutation-group.lisp (file)

Function: group-element-p PERM GROUP

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

Package
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
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
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
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
Source

orbit.lisp (file)

Function: group-identity GROUP

Return the identity element of the group GROUP.

Package
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
Source

orbit.lisp (file)

Function: group-order GROUP

Compute the order of the permutation group GROUP.

Package
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
Source

homomorphism.lisp (file)

Function: invert-slp SLP

Invert the SLP SLP.

Package
Source
Function: list-to-perm LIST

Construct a perm from a list LIST.

Package
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
Source
Function: make-cycle &rest ELEMENTS

Create a new cycle with the elements ELEMENTS.

Package
Source

permutation.lisp (file)

Function: make-free-group NUM-GENERATORS

Make a free group that contains NUM-GENERATORS generators.

Package
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
Source

free-group.lisp (file)

Function: make-perm &rest ELEMENTS

Construct a permutation from the numbers ELEMENTS.

Package
Source

permutation.lisp (file)

Function: make-perm-generator N

Create a generator that generates permutations of size N.

Package
Source
Function: make-perm-spec N

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

Package
Source

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

Package
Source
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
Source
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
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
Source

orbit.lisp (file)

Function: orbit-length N PERM

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

Package
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
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
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
Source

permutation.lisp (file)

Function: perm-conjugate P C

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

Package
Source

permutation.lisp (file)

Function: perm-eval PERM N

Evaluate the permutation PERM at index N.

Package
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
Source

permutation.lisp (file)

Function: perm-evaluator PERM

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

Package
Source

permutation.lisp (file)

Function: perm-evaluator* PERM

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

Package
Source

permutation.lisp (file)

Function: perm-even-p PERM

Is PERM an even permutation?

Package
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
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
Source

permutation.lisp (file)

Function: perm-identity N

The identity permutation of size N.

Package
Source

permutation.lisp (file)

Function: perm-identity-p PERM

Is the permutation PERM an identity permutation?

Package
Source

permutation.lisp (file)

Function: perm-inverse PERM

Find the inverse of the permutation PERM.

Package
Source

permutation.lisp (file)

Function: perm-inverse-eval PERM N

Evaluate the inverse of the permutation PERM at index N.

Package
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
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
Source

permutation.lisp (file)

Function: perm-length PERM

Count the number of inversions in the permutation PERM.

Package
Source

permutation.lisp (file)

Function: perm-odd-p PERM

Is PERM an odd permutation?

Package
Source

permutation.lisp (file)

Function: perm-order PERM

Compute the order of a permutation PERM.

Package
Source

permutation.lisp (file)

Function: perm-point-fixed-p PERM K

Is K fixed in the perm PERM?

Package
Source

permutation.lisp (file)

Function: perm-ref PERM N

Compute the zero-based index of PERM at N.

Package
Source

permutation.lisp (file)

Function: perm-sign PERM

The sign of a permutation PERM.

Package
Source

permutation.lisp (file)

Function: perm-size PERM

The size of a permutation PERM.

Package
Source

permutation.lisp (file)

Function: perm-to-list PERM

Convert a permutation PERM to a list representation.

Package
Source

permutation.lisp (file)

Function: perm-to-vector PERM

Convert a permutation PERM to a vector.

Package
Source

permutation.lisp (file)

Function: perm-transpose-entries PERM A B

Transpose the entries A and B in PERM.

Package
Source

permutation.lisp (file)

Function: perm-transpose-indexes PERM A B

Transpose the indexes A and B in PERM.

Package
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
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
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
Source

permutation.lisp (file)

Function: primitive-group-p GROUP

Is the perm group GROUP primitive?

Package
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
Source
Function: random-group-element GROUP

Generate a random element of the group GROUP.

Package
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
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
Source

permutation.lisp (file)

Function: slp-composition %0 %1
Package
Source
Function: slp-element %0
Package
Source
Function: slp-inversion %0
Package
Source
Function: slp-symbol %0
Package
Source
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
Source

orbit.lisp (file)

Function: subgroup-p GROUP SUBGROUP

Is the group SUBGROUP a subgroup of GROUP?

Package
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
Source
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
Source

symbol-assignment (function)

Function: to-cycles PERM &key CANONICALIZEP

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

Package
Source

permutation.lisp (file)

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

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

Package
Source

permutation-group.lisp (file)

Package
Source
Function: vector-to-perm WORD

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

Package
Source

permutation.lisp (file)

Function: vector-to-word-spec WORD

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

Package
Source

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
Source
Methods
Method: cardinality (SPEC word-spec)
Method: cardinality (SPEC combination-spec)
Method: cardinality (SPEC perm-spec)
Method: cardinality (SPEC combinatorial-spec) around
Generic Function: compose G A B

Compose two elements A and B within the group G.

Package
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
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
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
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
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
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
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
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)

Package
Methods

Source

Source
Generic Function: rank SPEC SET

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

Package
Source
Methods
Method: rank (SPEC word-spec) SET
Method: rank (SPEC combination-spec) SET
Method: rank (SPEC perm-spec) SET
Generic Function: size OBJECT
Package
Methods
Method: size (COMBINATORIAL-SPEC combinatorial-spec)

Source
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
Source
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
Source

permutation.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: canonicalized
Type

boolean

cycle-canonicalized (function)

Writers

(setf cycle-canonicalized) (function)

Slot: rep
Type

(vector cl-permutation:cycle-element)

Initform

#()

cycle-rep (function)

Writers

(setf cycle-rep) (function)

Structure: perm ()
Package
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)

perm.rep (function)

Writers

(setf perm.rep) (function)

Structure: slp ()
Package
Source
Direct superclasses

algebraic-data-type (structure)

Direct subclasses
Structure: slp-composition ()
Package
Source
Direct superclasses

slp (structure)

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

cl-permutation:slp

Initform

(error "unspecified field.")

slp-composition%0 (function)

Writers

(setf slp-composition%0) (function)

Slot: %1
Type

cl-permutation:slp

Initform

(error "unspecified field.")

slp-composition%1 (function)

Writers

(setf slp-composition%1) (function)

Structure: slp-element ()
Package
Source
Direct superclasses

slp (structure)

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

(error "unspecified field.")

slp-element%0 (function)

Writers

(setf slp-element%0) (function)

Structure: slp-inversion ()
Package
Source
Direct superclasses

slp (structure)

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

cl-permutation:slp

Initform

(error "unspecified field.")

slp-inversion%0 (function)

Writers

(setf slp-inversion%0) (function)

Structure: slp-symbol ()
Package
Source
Direct superclasses

slp (structure)

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

symbol

Initform

(error "unspecified field.")

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
Source
Direct superclasses

combinatorial-spec (class)

Direct methods
Direct slots
Slot: zero-count
Initargs

:zero-count

comb.zero-count (generic function)

Class: combinatorial-spec ()

Abstract class representing linear sequences of objects of size SIZE.

Package
Source
Direct superclasses

standard-object (class)

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

(or null unsigned-byte)

cardinality-cache (generic function)

Writers

(setf cardinality-cache) (generic function)

Slot: size
Initargs

:size

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
Source

free-group.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: num-generators
Initargs

:num-generators

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
Source

homomorphism.lisp (file)

Direct superclasses

homomorphism (class)

Direct methods
Direct slots
Slot: from-group

Preimage of the homomorphism.

Initargs

:from-group

homomorphism-preimage (generic function)

Slot: to-group

Image of the homomorphism.

Initargs

:to-group

homomorphism-image (generic function)

Slot: function

Homomorphism function.

Initargs

:function

homomorphism-function (generic function)

Class: generator-homomorphism ()

A perm group homomorphism constructed from images of its genertators.

This class is FUNCALLable.

Package
Source

homomorphism.lisp (file)

Direct superclasses

homomorphism (class)

Direct methods
Direct slots
Slot: from-group

Preimage of the homomorphism.

Initargs

:from-group

homomorphism-preimage (generic function)

Slot: to-group

Image of the homomorphism.

Initargs

:to-group

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

homomorphism-generator-map (generic function)

Package
Source
Direct superclasses

combinatorial-spec (class)

Direct methods
Direct slots
Initargs

Class: perm-group ()

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

Package
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

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

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

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

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

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

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

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
Source
Direct superclasses

combinatorial-spec (class)

Direct methods

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

Package
Source
Direct superclasses

combinatorial-spec (class)

Direct methods
Direct slots
Initargs

Class: slp-context ()

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

Package
Source
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))

symbol-table (generic function)

Writers

(setf symbol-table) (generic function)

Class: word-spec ()

Representation of a word of elements 1 to TYPES.

Package
Source
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

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

word.type-counts (generic function)

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

#### 5.1.7 Types

Type: cycle-element ()

An element of a cycle.

Package
Source

permutation.lisp (file)

Type: perm-element ()

An element of a perm.

Package
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
Source

permutation-group.lisp (file)

Special Variable: *perm-group-verbose*
Package
Source

permutation-group.lisp (file)

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

Print permutations with special permutation syntax?

Package
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
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
Source

permutation-group.lisp (file)

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

permutation.lisp (file)

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

block.lisp (file)

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

block.lisp (file)

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

permutation.lisp (file)

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

utilities.lisp (file)

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

permutation.lisp (file)

Function: abs> X Y
Package
Source
Function: add-generator PERM SGS TRANS K SLP
Package
Source

permutation-group.lisp (file)

Function: allocate-perm-vector N

Allocate a vector compatible with a size-N permutation.

Package
Source

permutation.lisp (file)

Function: array-for-spec SPEC &key INITIAL-ELEMENT
Package
Source
Function: assert-valid-permutation-elements ELEMENTS

Verify (via assertions) that the elements

Package
Source

permutation.lisp (file)

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
Source

block.lisp (file)

Function: binomial-coefficient-or-zero N K

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

Package
Source
Function: block-slot BLOCK-SUBSYSTEM BLK

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

Package
Source

block.lisp (file)

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

block.lisp (file)

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

block.lisp (file)

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

block.lisp (file)

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

block.lisp (file)

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

block.lisp (file)

Function: block-subsystem-p OBJECT
Package
Source

block.lisp (file)

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

block.lisp (file)

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

free-group.lisp (file)

Function: canonicalize-raw-block-subsystems BSS

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

Package
Source

block.lisp (file)

Function: check-cycle-elements ELEMENTS

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

Package
Source

permutation.lisp (file)

Function: clear-membership-set SET
Package
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
Source

permutation-group.lisp (file)

Function: compute-god-table GROUP &key TARGET VERBOSE
Package
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
Source

permutation.lisp (file)

Function: copy-block-subsystem INSTANCE
Package
Source

block.lisp (file)

Function: copy-cycle INSTANCE
Package
Source

permutation.lisp (file)

Function: copy-djs INSTANCE
Package
Source

block.lisp (file)

Function: copy-djs-rep INSTANCE
Package
Source

block.lisp (file)

Function: copy-perm INSTANCE
Package
Source

permutation.lisp (file)

Function: copy-queue INSTANCE
Package
Source

utilities.lisp (file)

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

permutation.lisp (file)

Function: cycle-p OBJECT
Package
Source

permutation.lisp (file)

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

permutation.lisp (file)

Function: dequeue QUEUE

Remove and return an element from the queue QUEUE.

Package
Source

utilities.lisp (file)

Function: djs VALUE

Construct a fresh DJS node.

Package
Source

block.lisp (file)

Function: djs-change-representative DJS

Change the representative of DJS to point to itself.

Package
Source

block.lisp (file)

Function: djs-find D

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

Package
Source

block.lisp (file)

Function: djs-p OBJECT
Package
Source

block.lisp (file)

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

block.lisp (file)

Function: djs-rep-p OBJECT
Package
Source

block.lisp (file)

Function: djs-representative INSTANCE
Function: (setf djs-representative) VALUE INSTANCE
Package
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
Source

block.lisp (file)

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

block.lisp (file)

Function: enqueue QUEUE OBJ

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

Package
Source

utilities.lisp (file)

Function: exists-mobile-p PERM LEN
Package
Source
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
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
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
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
Source

find-subgroups.lisp (file)

Function: generator-orders G

Return the orders of each generator of the group G.

Package
Source

find-subgroups.lisp (file)

Function: group-block-subsystems GROUP

Return a list of block subsystems of the group GROUP.

Package
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
Source

permutation-group.lisp (file)

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

do-group-elements.lisp (file)

Compute the radix of the group GROUP.

Package
Source

do-group-elements.lisp (file)

Function: iota N

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

Package
Source

utilities.lisp (file)

Function: iota+1 N

Generate a list of numbers between 1 and N.

Package
Source

utilities.lisp (file)

Function: iota-vector N

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

Package
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
Source

extra-functions.lisp (file)

Function: list-minimum LIST

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

Package
Source

utilities.lisp (file)

Function: list-to-queue LIST

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

Package
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
Source

block.lisp (file)

Function: make-membership-set SIZE
Package
Source

utilities.lisp (file)

Function: make-queue ()

Create a new empty queue.

Package
Source

utilities.lisp (file)

Function: make-sgs N

Make a strong generating set of size N.

Package
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
Source

permutation-group.lisp (file)

Function: make-transversal N

Make a transversal of size N.

Package
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
Source

permutation.lisp (file)

Function: map-exponent-subgroups F GROUP

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

Package
Source

find-subgroups.lisp (file)

Function: map-into-perm FUNCTION PERM-SPEC
Package
Source
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
Source

permutation.lisp (file)

Function: map-suitable-subgroups F GROUP

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

Package
Source

find-subgroups.lisp (file)

Function: maximum LIST &key KEY

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

Package
Source

utilities.lisp (file)

Function: membership-set-count SET
Package
Source

utilities.lisp (file)

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

utilities.lisp (file)

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

utilities.lisp (file)

Function: mobilep IDX PERM &optional LEN
Package
Source
Function: next-perm PERM LEN
Package
Source
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
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
Source

utilities.lisp (file)

Function: perm-eject PERM

Remove the largest element of a permutation.

Package
Source

extra-functions.lisp (file)

Function: perm-extend PERM &optional N

Extend a permutation PERM

Package
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
Source

extra-functions.lisp (file)

Function: perm-p OBJECT
Package
Source

permutation.lisp (file)

Package
Source

permutation.lisp (file)

Function: perm.rep INSTANCE
Function: (setf perm.rep) VALUE INSTANCE
Package
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
Source

permutation.lisp (file)

Function: print-perm PERM STREAM DEPTH

Printer for perms.

Package
Source

permutation.lisp (file)

Function: product SEQ &key KEY

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

Package
Source

utilities.lisp (file)

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

utilities.lisp (file)

Function: queue-empty-p QUEUE

Is the queue QUEUE empty?

Package
Source

utilities.lisp (file)

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

utilities.lisp (file)

Function: queuep OBJECT
Package
Source

utilities.lisp (file)

Function: random-between A B

Generate a random integer between A and B, inclusive.

Package
Source

utilities.lisp (file)

Function: random-element SEQ

Select a random element from the sequence SEQ.

Package
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
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
Source

permutation-group.lisp (file)

Function: reverse-direction IDX PERM
Package
Source
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
Source

permutation.lisp (file)

Function: sgs-ref SGS K
Function: (setf sgs-ref) NEW-VALUE SGS K
Package
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
Source

permutation-group.lisp (file)

Writer

(setf sigma) (function)

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

permutation-group.lisp (file)

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
Source

permutation-group.lisp (file)

Function: sign X

Return the sign of X.

Package
Source

utilities.lisp (file)

Function: singletonp X

Does X contain one element?

Package
Source

utilities.lisp (file)

Function: slp-composition%0 INSTANCE
Package
Source
Function: slp-composition%1 INSTANCE
Package
Source
Function: slp-element%0 INSTANCE
Package
Source
Function: slp-inversion%0 INSTANCE
Package
Source
Function: slp-symbol%0 INSTANCE
Package
Source
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
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
Source

find-subgroups.lisp (file)

Function: tau-symbol ()

Return a freshly made symbol for tau.

Package
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
Source

permutation-group.lisp (file)

Function: trans-element-p PERM TRANS &optional K
Package
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
Source

permutation-group.lisp (file)

Writer

(setf transversal-ref) (function)

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

permutation-group.lisp (file)

transversal-ref (function)

Function: trivial-block-system-p BS

Is the block system BS a trivial block system?

Package
Source

block.lisp (file)

Function: update-transversal PERM SGS TRANS K SLP
Package
Source

permutation-group.lisp (file)

Function: word-generator GROUP
Package
Source

permutation-group.lisp (file)

Function: word-length W
Package
Source

permutation-group.lisp (file)

Function: zero-array LENGTH

Make an array of zeroes of length LENGTH.

Package
Source

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
Methods
Method: cardinality-cache (COMBINATORIAL-SPEC combinatorial-spec)

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

automatically generated writer method

Source
Generic Function: comb.zero-count OBJECT
Package
Methods
Method: comb.zero-count (COMBINATION-SPEC combination-spec)

Source
Generic Function: free-group-num-generators OBJECT
Package
Methods
Method: free-group-num-generators (FREE-GROUP free-group)

Source

free-group.lisp (file)

Generic Function: god-table-generators OBJECT
Package
Methods
Method: god-table-generators (GOD-TABLE god-table)

Source

god.lisp (file)

Generic Function: god-table-group OBJECT
Package
Methods
Method: god-table-group (GOD-TABLE god-table)

Source

god.lisp (file)

Generic Function: god-table-target OBJECT
Package
Methods
Method: god-table-target (GOD-TABLE god-table)

Source

god.lisp (file)

Generic Function: god-table-vector OBJECT
Package
Methods
Method: god-table-vector (GOD-TABLE god-table)

Source

god.lisp (file)

Generic Function: homomorphism-function OBJECT
Package
Methods
Method: homomorphism-function (FUNCTION-HOMOMORPHISM function-homomorphism)

Homomorphism function.

Source

homomorphism.lisp (file)

Generic Function: homomorphism-generator-map OBJECT
Package
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
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
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
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
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
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
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
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
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
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
Generic Function: word.type-counts OBJECT
Package
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
Generic Function: word.types OBJECT
Package
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

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
Source

block.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: group

block-subsystem-group (function)

Writers

(setf block-subsystem-group) (function)

Slot: base-block

block-subsystem-base-block (function)

Writers

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

Slot: size

block-subsystem-size (function)

Writers

(setf block-subsystem-size) (function)

Slot: block-size

block-subsystem-block-size (function)

Writers

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

Slot: orbit

block-subsystem-orbit (function)

Writers

(setf block-subsystem-orbit) (function)

Slot: block-slots

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
Source

block.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: representative
Type

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

djs-representative (function)

Writers

(setf djs-representative) (function)

Slot: value

djs-value (function)

Writers

(setf djs-value) (function)

Structure: djs-rep ()

Pointer to the representative element of a DJS.

Package
Source

block.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: djs
Type

cl-permutation::djs

djs-rep-djs (function)

Writers

(setf djs-rep-djs) (function)

Structure: queue ()
Package
Source

utilities.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: elements
Type

list

queue-elements (function)

Writers

(setf queue-elements) (function)

Slot: last
Type

(or null (cons t null))

queue-last (function)

Writers

(setf queue-last) (function)

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

#### 5.2.5 Classes

Class: god-table ()
Package
Source

god.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: group
Initargs

:group

god-table-group (generic function)

Slot: table
Initargs

:table

god-table-vector (generic function)

Slot: target
Initargs

:target

god-table-target (generic function)

Slot: generators
Initargs

:generators

god-table-generators (generic function)

Class: homomorphism ()
Package
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
Source

permutation.lisp (file)

Type: sgs ()
Package
Source

permutation-group.lisp (file)

Type: transversal ()
Package
Source

permutation-group.lisp (file)

Type: vector-index ()

Possible indexes to a vector.

Package
Source

utilities.lisp (file)

Type: vector-size &key DOWN-BY

Possible sizes of a vector.

Package
Source

utilities.lisp (file)

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

## Appendix A Indexes

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

### A.1 Concepts

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
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
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
Jump to: B   C   D   F   G   H   M   P   Q   R   S   T   V   W