Discrete helpers/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

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 SetPart objects are equal. The labels are additional information.

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 block_labels is a bidict from blocks (converted to tuples for technical reasons) to labels.

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

meet and join

set_part/methods/meet_and_join

The meet and join methods can be used to combine two partitions into one.

The meet $\land$ (greatest lower bound) is the coarsest partition finer than both.
The join $\lor$ (least upper bound) is the finest partition coarser than both.

The meet is easy to calculate. The join is currently expensive, and will hopefully be improved.

example

from discretehelpers.set_part import SetPart


red = SetPart([[0, 1, 2, 4], [5, 6, 9], [7, 8]])
green = SetPart([[0, 1], [2, 3, 4], [6, 8, 9]])

assert red.join(green) == SetPart([[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]])
assert red.meet(green) == SetPart([[0, 1], [2, 4], [6, 9]])

meet

The default partition is the finest, and it can be made coarser. But one can not start with the coarsest, and make it finer. (Although theoretically there would be nothing wrong with that.)
This method is a way to make blocks smaller instead of bigger.

find intersections

This example shows how to find all intersections of three sets. (This is related to Boolf.)

from discretehelpers.set_part import SetPart


a = {'Donald', 'Daisy', 'Huey', 'Dewey', 'Louie', 'Pluto'}
b = {'Donald', 'Daisy', 'Scrooge', 'Della', 'Gladstone', 'Gyro', 'Pluto'}
c = {'Mickey', 'Minnie', 'Gladstone', 'Gyro', 'Huey', 'Dewey', 'Louie', 'Pluto'}
universe = a | b | c

assert universe == {'Donald', 'Daisy', 'Scrooge', 'Della', 'Gladstone', 'Gyro', 'Mickey', 'Minnie', 'Huey', 'Dewey', 'Louie', 'Pluto'}

a_part = SetPart([a, universe-a], domain=universe)
b_part = SetPart([b, universe-b], domain=universe)
c_part = SetPart([c, universe-c], domain=universe)

combined_part = a_part.meet(b_part).meet(c_part)

assert combined_part.blocks_with_singletons() == [['Daisy', 'Donald'], ['Della', 'Scrooge'], ['Dewey', 'Huey', 'Louie'], ['Gladstone', 'Gyro'], ['Mickey', 'Minnie'], ['Pluto']]

show intersections

A Venn diagram of three sets has seven cells, not counting the one outside.
The following code shows the names assigned to their cells. (The one only in set A is empty.)

def block_to_cell(block):
    s = ''
    s += 'A' if set(block).issubset(a) else ''
    s += 'B' if set(block).issubset(b) else ''
    s += 'C' if set(block).issubset(c) else ''
    return s

for block in combined_part.blocks_with_singletons():
    print(block_to_cell(block), '-->', block)

AB --> ['Daisy', 'Donald']
B --> ['Della', 'Scrooge']
AC --> ['Dewey', 'Huey', 'Louie']
BC --> ['Gladstone', 'Gyro']
C --> ['Mickey', 'Minnie']
ABC --> ['Pluto']