View source for Discrete helpers/set part

{{dh-link|set_part}}
This class implements [[w:Partition of a set|set partitions]], which are essentially the same as {{w|equivalence class}}es.<br>
The partitioned set (called ''domain'') is usually that of non-negative integers.

<syntaxhighlight lang="python">
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]]
</syntaxhighlight>

==Cayley tables==

[[File:Symmetric group 3; Cayley table; matrices (left).svg|thumb|400px|Cayley table of the Symmetric group S<sub>3</sub>]]

<code>SetPart</code> can be used to model the {{w|Cayley table}} of a group.<br>
It makes sense to use a set of simple IDs for the elements of the group. <small>(Typically that should be integers or pairs of integers.)</small><br>
Then the <code>domain</code> argument is the Cartesian square of the set of IDs.<br>
The entries of the Cayley table are IDs added as labels to the blocks.<br>
The method <code>add_label_to_element</code> will take care of creating the blocks.

Let <code>id_to_perm</code> be a <code>bidict</code> from IDs to permutations.

<syntaxhighlight lang="python">
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)
</syntaxhighlight>

{{Collapsible START|blocks and block labels|collapsed light}}
Only the blocks decide if two <code>SetPart</code> objects are equal. The labels are additional information.

<syntaxhighlight lang="python">
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))
)
</syntaxhighlight>

The attribute <code>block_labels</code> is a bidict from blocks <small>(converted to tuples for technical reasons)</small> to labels.

<syntaxhighlight lang="python">
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
}
</syntaxhighlight>
{{Collapsible END}}

What are the products of permutations 3 and 5?

<syntaxhighlight lang="python">
assert cayley.get_label_from_element((3, 5)) == 1
assert cayley.get_label_from_element((5, 3)) == 2
</syntaxhighlight>

Which (other) products create the permutations 1 and 2?

<syntaxhighlight lang="python">
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)]
</syntaxhighlight>


==meet and join==
{{dh-link|set_part/methods/meet_and_join}}
The {{w|join and meet|meet and join}} methods can be used to combine two partitions into one.
* The '''meet''' <math>\land</math> <small style="opacity: .7;">(greatest lower bound)</small> is the coarsest partition finer than both.
* The '''join''' <math>\lor</math> <small style="opacity: .7;">(least upper bound)</small> is the finest partition coarser than both.

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

{{Collapsible START|example|collapsed}}
{|
|style="vertical-align: top;"|
<syntaxhighlight lang="python">
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]])
</syntaxhighlight>
| [[File:Join and meet of a partition of a 10-set.svg|thumb|red and green with brown intersection]]
|}
{{Collapsible END}}

===meet===

<small>The default partition is the finest, and it can be made coarser. But one can not start with the coarsest, and make it finer. <small style="opacity: .5;">(Although theoretically there would be nothing wrong with that.)</small></small><br>
This method is a way to make blocks smaller instead of bigger.<br>

{{Collapsible START|find intersections|collapsed}}
This example shows how to find all intersections of three sets. &nbsp; <small>(This is related to [[Discrete helpers/boolf|Boolf]].)</small>

<syntaxhighlight lang="python">
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']]
</syntaxhighlight>

{{Collapsible START|show intersections|collapsed light}}
{|
|
A Venn diagram of three sets has seven cells, not counting the one outside.<br>
The following code shows the names assigned to their cells. <small>(The one only in set A is empty.)</small><br>
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

<pre>
AB --> ['Daisy', 'Donald']
B --> ['Della', 'Scrooge']
AC --> ['Dewey', 'Huey', 'Louie']
BC --> ['Gladstone', 'Gyro']
C --> ['Mickey', 'Minnie']
ABC --> ['Pluto']
</pre>
|style="vertical-align: top;"| [[File:Venn numbered.svg|thumb|Venn diagram]]
|}
{{Collapsible END}}
{{Collapsible END}}


[[Category:Discrete helpers (software documentation)]]