cayleypy.PermutationGroups
- class cayleypy.PermutationGroups[source]
Pre-defined Cayley graphs for permutation groups (S_n).
- __init__()
Methods
__init__()all_cycles(n)Cayley graph for S_n (n ≥ 2), generated by all cycles of length 2 to n.
Cayley graph for S_n (n>=2), generated by all n(n-1)/2 transpositions.
Cayley graph for S_n (n>=2), generated by interchanges of all possible pairs of substrings.
Cayley graph generated by reverses of all signed prefixes.
conjugacy_classes(n, classes)A conjugacy class of S_n is a subset of permutations with same set of cycle lengths.
consecutive_k_cycles(n, k)Cayley graph for S_n generated by all consecutive k-cycles: (i, i+1, ..., i+k-1) for i = 0..n-k.
coxeter(n)Cayley graph for S_n (n>=2), generated by adjacent transpositions (Coxeter generators).
cubic_pancake(n, subset)Cayley graph for S_n (n>=2), generated by set of 3 prefix reversal generators.
Cayley graph for S_n (n>=2), generated by adjacent transpositions plus cyclic transposition.
derangements(n)Cayley graph generated by permutations without fixed points, called derangements.
down_cycles(n)Cayley graph generated by all downcycles in S_n: (i, i+1, ..., j), 0 <= i < j < n.
Cayley graph for S_n (n>=2), generated by reverses of all possible n(n-1)/2 substrings.
generalized_stars(n[, k])Cayley graph generated by generalized star permutations.
increasing_k_cycles(n, k)Cayley graph for S_n generated by all increasing k-cycles (c_1 c_2 .
Cayley graph generated by involutive derangements.
koltsov3(n[, perm_type, k, d])The set of generators ”Koltsov3” consists of 3 involutions.
larx(n)Cayley graph for S_n (n >= 2), generated by transposition-based permutations.
lrx(n[, k])Cayley graph for S_n (n>=3), generated by: shift left, shift right, swap two elements 0 and k.
lx(n)Cayley graph for S_n (n>=3), generated by left shift (L) and swapping first two elements (X).
pancake(n)Cayley graph for S_n (n>=2), generated by reverses of all prefixes.
Cayley graph generated by all prefix cycles in S_n: (0 1 .
rand_generators(n, k)Cayley graph for S_n generated by k random permutations
rapaport_m1(n)Cayley graph for S_n with M1 generators.
rapaport_m2(n)Cayley graph for S_n with M2 generators.
sheveleva2(n, k)"Sheveleva2" generators consist of only 2 elements and have two parameters: n and k.
Cayley graph generated by reverses of all possible signed n(n+1)/2 substrings.
stars(n)Cayley graph generated by stars permutations.
three_cycles(n)Cayley graph for S_n (n ≥ 3), generated by all 3-cycles (a, b, c) where a < b, a < c.
three_cycles_01i(n[, add_inverses])Cayley graph for A_n (n>=3), generated by cycles (0 1 i) for 2<=i<n.
Cayley graph for S_n (n ≥ 3), generated by 3-cycles of the form (0 i j), where i != j.
top_spin(n[, k])Cayley graph for S_n (n>=k>=2), generated by: shift left, shift right, reverse first k elements.
transposons(n)Cayley graph for S_n (n>=2), generated by transpositions of all possible substrings to all possible places.
wrapped_k_cycles(n, k)Cayley graph for S_n (n >= 2, 2 <= k <= n), generated by all consecutive k-cycles with wrap-around.
- static all_cycles(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n ≥ 2), generated by all cycles of length 2 to n.
- static all_transpositions(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by all n(n-1)/2 transpositions.
- static block_interchange(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by interchanges of all possible pairs of substrings. https://arxiv.org/pdf/0811.0740
- static burnt_pancake(n: int) CayleyGraphDef[source]
Cayley graph generated by reverses of all signed prefixes.
Actually is a graph for S_2n (n>=1) representing a graph for n pancakes, where i-th element represents bottom side of i-th pancake, and (n+i)-th element represents top side of i-th pancake. The graph has n generators denoted R1,R2..R(n), where Ri is reverse of elements 0,1..i,n,n+1..n+i.
- static conjugacy_classes(n: int, classes: dict[tuple[int], int | None]) CayleyGraphDef[source]
A conjugacy class of S_n is a subset of permutations with same set of cycle lengths.
- Each entry (key, value) of classes dict specifies a conjugacy class:
- key, tuple[int]: cycle lengths, contains positive integers, the order does not matter, e.g.
(4,3,3) class have 2 cycles of length 3 (3-cycle) and one 4-cycle. sum(key) must be <= n; if sum(key) < n, the remaining elements are treated as 1-cycles (fixed elements).
- value, int or None: the number of generators randomly sampled from the class specified by key.
If None, all permutations are taken.
Examples:
- n = 6, classes = {(3,2): None}:
takes all permutations from S_6 with one 3-cycles, one 2-cycle, and one fixed element.
- n = 8, classes = {(3,2,3): None}:
takes all permutations from S_8 with two 3-cycles and one 2-cycle.
- n = 9, classes = {(4,): None}:
takes all permutations from S_9 with one 4-cycle and five fixed elements.
- n = 23, classes = {(1,3,1,5,3,5,4,1): 3}:
takes three random permutations from S_23 with two 3-cycles, one 4-cycle, two 5-cycles, and three 1-cycles.
- n = 4, classes = {(2,2): None, (3,): 5}:
takes all permutations from S_4 with two 2-cycles and 5 random permutations with one 3-cycle.
- n = 10, classes = {(3,3,4): None, (1,1,2,2,2): None, (10,): 2}
takes all permutations from S_10 with two 3-cycles and one 4-cycle, all permutations three 2-cycles and four fixed elemens, and 2 random permutations with one 10-cycle.
N.B. The set of cycle lengths of a permutation from S_n forms a partition of n (https://oeis.org/A000041)
- static consecutive_k_cycles(n: int, k: int) CayleyGraphDef[source]
Cayley graph for S_n generated by all consecutive k-cycles: (i, i+1, …, i+k-1) for i = 0..n-k.
- static coxeter(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by adjacent transpositions (Coxeter generators).
It has n-1 generators: (0,1), (1,2), …, (n-2,n-1).
- static cubic_pancake(n: int, subset: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by set of 3 prefix reversal generators.
- Sets definitions are:
subset=1 => {Rn, R(n-1), R2}
subset=2 => {Rn, R(n-1), R3}
subset=3 => {Rn, R(n-1), R(n-2)}
subset=4 => {Rn, R(n-1), R(n-3)}
subset=5 => {Rn, R(n-2), R2}
subset=6 => {Rn, R(n-2), R3}
subset=7 => {Rn, R(n-2), R(n-3)}
where Ri is reverse of elements 0,1..i.
- static cyclic_coxeter(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by adjacent transpositions plus cyclic transposition.
It has n generators: (0,1), (1,2), …, (n-2,n-1), (0,n-1).
- static derangements(n: int) CayleyGraphDef[source]
Cayley graph generated by permutations without fixed points, called derangements.
- static down_cycles(n: int) CayleyGraphDef[source]
Cayley graph generated by all downcycles in S_n: (i, i+1, …, j), 0 <= i < j < n.
- static full_reversals(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by reverses of all possible n(n-1)/2 substrings.
- static generalized_stars(n: int, k: int = 1) CayleyGraphDef[source]
Cayley graph generated by generalized star permutations. Builds transpositions swapping each of the first k indices with each of the remaining n-k indices, i.e. (i <-> j) for i in [0, k-1], j in [k, n-1].
- static increasing_k_cycles(n: int, k: int) CayleyGraphDef[source]
Cayley graph for S_n generated by all increasing k-cycles (c_1 c_2 … c_k) with 0 <= c_1 < c_2 < … < c_k < n.
- static involutive_derangements(n: int) CayleyGraphDef[source]
Cayley graph generated by involutive derangements.
- static koltsov3(n: int, perm_type: int = 2, k: int = 1, d: int = 1)[source]
The set of generators ”Koltsov3” consists of 3 involutions.
There are several varieties, depending on the “type”.
One generator starts with two involutions both of which are products of (i, i+1), but one is for all even i (“I” generator), whereas the other one is for odd i (“K” generator).
The third involution ”S” (swap) which is a short product of transpositions that differs depending on the parameter ”type”. For type 1, ”S” is just 1 transposition (k, k + d). It also dependig on the parameter d. For type 2 it is a product of 2 transpositions: (k, k + 3) and (k + 1, k + 2).
- Parameters:
n – length of permutations.
perm_type – type of S generator.
k – additional parameter for S generator.
d – additional parameter for type 1.
- static larx(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n >= 2), generated by transposition-based permutations. Creates two generators: one with 0,1 transposition and one with cyclic shift.
- static lrx(n: int, k: int = 1) CayleyGraphDef[source]
Cayley graph for S_n (n>=3), generated by: shift left, shift right, swap two elements 0 and k.
- Parameters:
n – Size of permutations.
k – Specifies that X is transposition of elements 0 and k. 1<=k<n. By default, k=1, which means X is transposition of first 2 elements.
- static lx(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=3), generated by left shift (L) and swapping first two elements (X).
This is an example of a Cayley graph where generators are not inverse-closed.
- Parameters:
n – Size of permutations.
- static pancake(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by reverses of all prefixes.
It has n-1 generators denoted R1,R2..R(n-1), where Ri is reverse of elements 0,1..i. See https://en.wikipedia.org/wiki/Pancake_graph.
- static prefix_cycles(n: int) CayleyGraphDef[source]
Cayley graph generated by all prefix cycles in S_n: (0 1 … j-1), j = 2..n.
- static rand_generators(n: int, k: int) CayleyGraphDef[source]
Cayley graph for S_n generated by k random permutations
- static rapaport_m1(n: int) CayleyGraphDef[source]
Cayley graph for S_n with M1 generators.
Reference: E. Rapaport-Strasser. Cayley color groups and hamilton lines. Scr. Math, 24:51–58, 1959.
- static rapaport_m2(n: int) CayleyGraphDef[source]
Cayley graph for S_n with M2 generators.
Reference: E. Rapaport-Strasser. Cayley color groups and hamilton lines. Scr. Math, 24:51–58, 1959.
- static sheveleva2(n: int, k: int) CayleyGraphDef[source]
“Sheveleva2” generators consist of only 2 elements and have two parameters: n and k.
One generator (A) is always an involution. The other (S) is a product of transpositions and one 4-cycle.
The construction is as follows:
Starting with 0, transpositions (i, i+1) are created.
These transpositions are assigned to generators one by one. The first transposition (0,1) is assigned to one generator, the second (1,2) to another, the third (2,3) to the first again, and so on.
When the process reaches index k, a 4-cycle (k-1, k, k+1, k+2) is created, which is added to the current generator.
After this, the alternate creation and assignment continues. transpositions (i, i+1).
The process stops when n is reached.
The final generators are obtained by multiplying all the permutations assigned to them.
- Parameters:
n – length of permutations.
k – additional parameter, “square position”.
- static signed_reversals(n: int) CayleyGraphDef[source]
Cayley graph generated by reverses of all possible signed n(n+1)/2 substrings.
Actually is a graph for S_2n (n>=1) representing a graph for n elements, where i-th index represents bottom side of i-th element, and (n+i)-th index represents top side of i-th element. The graph has n generators denoted R[1..1],R[1..2]..R[n..n], where R[i..j] is signed reverse of elements i,i+1..j (or actually indexes i..j,n+i..n+j).
- static stars(n: int) CayleyGraphDef[source]
Cayley graph generated by stars permutations.
- static three_cycles(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n ≥ 3), generated by all 3-cycles (a, b, c) where a < b, a < c.
- static three_cycles_01i(n: int, add_inverses: bool = True) CayleyGraphDef[source]
Cayley graph for A_n (n>=3), generated by cycles (0 1 i) for 2<=i<n.
- Parameters:
n – Size of permutations.
add_inverses – Whether inverse cycles are added when generating the graph.
- static three_cycles_0ij(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n ≥ 3), generated by 3-cycles of the form (0 i j), where i != j.
- static top_spin(n: int, k: int = 4)[source]
Cayley graph for S_n (n>=k>=2), generated by: shift left, shift right, reverse first k elements.
- Parameters:
n – Size of permutations.
k – Specifies size of prefix to reverse. By default, k=4.
- static transposons(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by transpositions of all possible substrings to all possible places.
- static wrapped_k_cycles(n: int, k: int) CayleyGraphDef[source]
Cayley graph for S_n (n >= 2, 2 <= k <= n), generated by all consecutive k-cycles with wrap-around.