cayleypy.PermutationGroups
- class cayleypy.PermutationGroups[source]
Pre-defined Cayley graphs for permutation groups (S_n).
- __init__()
Methods
__init__()Cayley graph for S_n (n>=2), generated by all n(n-1)/2 transpositions.
Cayley graph generated by reverses of all signed prefixes.
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.
Cayley graph for S_n (n>=2), generated by reverses of all possible n(n-1)/2 substrings.
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.
rapaport_m2(n)Cayley graph for S_n with M2 generators.
Cayley graph generated by reverses of all possible signed n(n+1)/2 substrings.
three_cycles(n)Cayley graph for S_n (n ≥ 3), generated by all 3-cycles (a, b, c) where a < b, a < c.
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.
- static all_transpositions(n: int) CayleyGraphDef[source]
Cayley graph for S_n (n>=2), generated by all n(n-1)/2 transpositions.
- 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 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 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 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 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 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 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_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.