Public
Edited
Oct 30, 2023
Importers
zip = (a, b) => a.map((k, i) => [k, b[i]])
arrayRotate = (x, k) => x.slice(k, x.length).concat(x.slice(0, k))
hasDuplicates = (array) => (new Set(array)).size !== array.length
mapOrId = function(f, x) {
return f.get(x) || x
}
// composeMap(m1, m2).get(v) = m2.get(m1.get(v)), when all of these are in the domain of definition of the various maps
composeMap = function(m1, m2) {
// Same approach as https://stackoverflow.com/questions/32000865/simplest-way-to-merge-es6-maps-sets
const output = new Map()
for (const k of new Set([...m1.keys(), ...m2.keys()])) {
const v = mapOrId(m2, mapOrId(m1, k))
if (k !== v) {output.set(k, v)}
}
return output
}
// Whether conjugation and commutators should put inverses last (i.e. on the right) or first (i.e. on the left)
conventionInverseLast = true
class Permutation {
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes#field_declarations
value;
string;
constructor(x) {
if (x instanceof Map) {
this.value = x
} else if (typeof x === 'string') {
this.value = x
.split(/[()]/).filter(s => s.length > 0)
.map(s => {if (/[ ,]/.test(s)) {return s.split(/[ ,]+/)} else {return Array.from(s)}})
.flatMap(a => {if (hasDuplicates(a)) {throw Error("duplicates in input")}; return new Map(zip(a, arrayRotate(a, 1)))})
.reduce(composeMap, new Map())
} else {
throw Error("unknown input")
}
this.string = printPermFromMap(this.value)
}
compose(q) {
return new Permutation(composeMap(this.value, q.value))
}
inverse() {
return new Permutation(new Map([...this.value.entries()].map(([k, v]) => [v, k])))
}
conj(q) {
if (conventionInverseLast) {
// There are two conventions for this (https://en.wikipedia.org/wiki/Commutator#Group_theory)
// Sticking with the same convention as for conjugation (inverses on the right), we'll define the commutator [p, q] as p q p^{-1} q^{-1}
return q.compose(this).compose(q.inverse())
} else {
return q.inverse().compose(this).compose(q)
}
}
}
commutator = {
if (conventionInverseLast) {
// There are two conventions for this (https://en.wikipedia.org/wiki/Commutator#Group_theory)
// Sticking with the same convention as for conjugation (inverses on the right), we'll define the commutator [p, q] as p q p^{-1} q^{-1}
return (p, q) => q.conj(p).compose(q.inverse())
} else {
return (p, q) => p.inverse().compose(p.conj(q))
}
}
r1 = new Permutation("(123)")
r2 = new Permutation("456")
r3 = new Permutation("789")
c1 = new Permutation("147")
c2 = new Permutation("258")
c3 = new Permutation("369")
// Taking the inverse reverses each cycle
r1.inverse()
// Non-overlapping cycles commute
r1.compose(r2) // Same as r2.compose(r1)
// Another way of expressing this: the commutator of non-overlapping cycles is the identity
commutator(r1, r2)
// Commutator written out in full
r1.compose(r2).compose(r1.inverse()).compose(r2.inverse())
// r1 is (123), c1 is (147)
// These overlap in exactly one item, 1
// Their product r1 . c1 maps:
// 1 to r1(1) = 2
// 2 to r1(2) = 3
// 3 to c1(r1(3)) = 4 (we have 3 => 1 => 4, with the overlap 1 in the middle)
// 4 to c1(4) = 7
// 7 to c1(7) = 1
r1.compose(c1)
// r1 is (123), c1 is (147)
// These overlap in exactly one item, 1
// Their product c1 . r1 maps:
// 1 to c1(1) = 4
// 4 to c1(4) = 7
// 7 to r1(c1(7)) = 2 (we have 7 => 1 => 2, with the overlap 1 in the middle)
// 2 to r1(2) = 3
// 3 to r1(3) = 1
c1.compose(r1)
// r1 is (123), c1 is (147)
// These overlap in exactly one element, 1
//
// The commutator r1 . c1 . r1^{-1} . c1^{-1} = (r1 . c1) . (c1 . r1)^{-1} maps:
// 1 to c1^{-1}(1) = 7 (we have 1 => 2 => 2 => 1 => 7, starting with the overlap 1)
// 7 to r1^{-1}(c1(7)) = r1^{-1}(1) = 3 (we have 7 => 7 => 1 => 3 => 3, with the overlap 1 in the middle)
// 3 to r1(1) = 1 (we have 3 => 1 => 4 => 4 => 1, ending with the overlap 1)
//
// So the commutator is the 3-cycle (1, c1^{-1}(1), r1^{-1}(1))
commutator(r1, c1)
// r1 is (123), c2 is (258)
// These overlap in exactly one element, 2
// And the commutator is the 3-cycle (2, c2^{-1}(2), r1^{-1}(2))
commutator(r1, c2)
// commutator(r1, c2) is (128), r3 is (789)
// Conjugating by r3 changes the '8' in the initial cycle to r3^{-1}(8) = 7
commutator(r1, c2).conj(r3)
// E.g. the diagonal 3-cycle (159) is
r1.conj(c2.inverse()).conj(c3) // All items in different rows and columns
// E.g. the wedge-shaped 3-cycle (126) is
r1.conj(c3.inverse()) // 2 items in the same row, 3rd item in a different row not sharing a column w/previous items
// E.g. the L-shaped 3-cycle (124) is
commutator(c1.inverse(), r1.inverse()) // 2 items in the same row, 3rd item in a different row sharing a column w/previous items
// And I-shaped 3-cycles like (123) are extremely easy, as they're all either generators or inverses of generators
r1 // 3 items in the same row
c3.compose(r1).compose(r2).compose(r3)
// Another construction of this element
r1.compose(r2).compose(r3).compose(c1)
notebookFormatting({max_width: 1050})
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
