Discrete helpers/set part
set_part |
This class implements set partitions, which are essentially the same as equivalence classes.
The partitioned set (called domain) is usually that of non-negative integers.
from discretehelpers.set_part import SetPart
sp = SetPart()
assert sp == SetPart([])
sp.merge_pair(3, 5)
assert sp == SetPart([[3, 5]])
sp.merge_many([7, 8, 9])
assert sp == SetPart([[3, 5], [7, 8, 9]])
assert sp.blocks_with_singletons(10) == [[0], [1], [2], [3, 5], [4], [6], [7, 8, 9]]
sp.merge_pair(5, 7)
assert sp == SetPart([[3, 5, 7, 8, 9]])
assert sp.blocks_with_singletons(10) == [[0], [1], [2], [3, 5, 7, 8, 9], [4], [6]]
Cayley tables[edit | edit source]
SetPart
can be used to model the Cayley table of a group.
It makes sense to use a set of simple IDs for the elements of the group. (Typically that should be integers or pairs of integers.)
Then the domain
argument is the Cartesian square of the set of IDs.
The entries of the Cayley table are IDs added as labels to the blocks.
The method add_label_to_element
will take care of creating the blocks.
Let id_to_perm
be a bidict
from IDs to permutations.
from itertools import product
from discretehelpers.set_part import SetPart
from discretehelpers.perm import Perm
from discretehelpers.a import rev_colex_perms
perms_raw = rev_colex_perms(3)
perms = [Perm(list(_)) for _ in perms_raw]
domain = list(product(range(6), repeat=2)) # all pairs (a, b) with a, b in 0...5
cayley = SetPart(blocks=[], domain=domain)
for index_a in range(6):
perm_a = perms[index_a]
for index_b in range(6):
perm_b = perms[index_b]
perm_ab = perm_a * perm_b
index_ab = perms.index(perm_ab)
cayley.add_label_to_element(element=(index_a, index_b), label=index_ab)
blocks and block labels |
---|
Only the blocks decide if two assert cayley == SetPart(
[
[(0, 0), (1, 1), (2, 2), (3, 4), (4, 3), (5, 5)],
[(0, 1), (1, 0), (2, 3), (3, 5), (4, 2), (5, 4)],
[(0, 2), (1, 4), (2, 0), (3, 1), (4, 5), (5, 3)],
[(0, 3), (1, 5), (2, 1), (3, 0), (4, 4), (5, 2)],
[(0, 4), (1, 2), (2, 5), (3, 3), (4, 0), (5, 1)],
[(0, 5), (1, 3), (2, 4), (3, 2), (4, 1), (5, 0)]
],
set(product(range(6), repeat=2))
)
The attribute assert dict(cayley.block_labels) == {
((0, 0), (1, 1), (2, 2), (3, 4), (4, 3), (5, 5)): 0,
((0, 1), (1, 0), (2, 3), (3, 5), (4, 2), (5, 4)): 1,
((0, 2), (1, 4), (2, 0), (3, 1), (4, 5), (5, 3)): 2,
((0, 3), (1, 5), (2, 1), (3, 0), (4, 4), (5, 2)): 3,
((0, 4), (1, 2), (2, 5), (3, 3), (4, 0), (5, 1)): 4,
((0, 5), (1, 3), (2, 4), (3, 2), (4, 1), (5, 0)): 5
}
|
What are the products of permutations 3 and 5?
assert cayley.get_label_from_element((3, 5)) == 1
assert cayley.get_label_from_element((5, 3)) == 2
Which (other) products create the permutations 1 and 2?
assert cayley.get_block_from_label(1) == [(0, 1), (1, 0), (2, 3), (3, 5), (4, 2), (5, 4)]
assert cayley.get_block_from_label(2) == [(0, 2), (1, 4), (2, 0), (3, 1), (4, 5), (5, 3)]