Discrete helpers/set part comp

This class extends set partitions (SetPart) with a complement relationship between the blocks of equivalent elements.

This can be used to save equality and complement relationships between arguments of Boolean functions (Boolf).

The initial object in the following example has three blocks. The first two of them are complements.

from discretehelpers.set_part_comp import SetPartComp


x = SetPartComp([[0, 1], [2, 3], [4, 5]], {(0, 2)})

assert x.are_equal(0, 1)
assert x.are_equal(2, 3)
assert x.are_equal(4, 5)

assert x.are_comp(0, 2)
assert x.are_comp(0, 3)
assert x.are_comp(1, 2)
assert x.are_comp(1, 3)

assert x.get_comp(0) == x.get_comp(1) == 2  # smallest element of the complementary block
assert x.get_comp(2) == x.get_comp(3) == 0
assert x.get_comp(4) is x.get_comp(5) is None  # no complement for this block

assert x.get_block(2) == [2, 3]  # block that contains the argument
assert x.get_repr(3) == 2  # smallest element of the block that contains the argument

x.set_equal(5, 6)
assert x == SetPartComp([[0, 1], [2, 3], [4, 5, 6]], {(0, 2)})
x.set_comp(6, 9) 
assert x == SetPartComp([[0, 1], [2, 3], [4, 5, 6]], {(0, 2), (4, 9)})

assert x.are_equal(4, 6)
assert x.are_comp(5, 9)

assert not x.are_equal(3, 4)
assert not x.are_comp(3, 4)

domain

The domain is the set of integers, including the negative ones. (This is different from SetPart, where the domain can be changed, and is N by default.)
This class was developed to deal with the blight of a Boolean function.
That includes blotted Boolean functions, where the arguments can be equal or complementary to the universe, which is represented by −1.

blotted BF with empty set
bad Euler diagram with nothing in set C In this Boolean function the set C is empty, and thus complementary to the universe. C is represented by 2. So 2 and −1 are complements. from discretehelpers.boolf.examples import fobope assert fobope.blight == SetPartComp([], {(-1, 2)})

blotted BF with universal set
bad Euler diagram with everything in set H In this Boolean function the set H is equal to the universe. H is represented by 7. So 7 and −1 are in the same block. from discretehelpers.boolf.examples import lapava assert lapava.blot == SetPartComp([[-1, 7]])

methods

related set partition

related_part is a derived SetPart, where complementary blocks are merged.
There are related methods like number_of_related_blocks.

example

from discretehelpers.set_part import SetPart


x = SetPartComp([[0, 1], [2, 3], [4, 5, 6]], {(0, 2), (4, 9)})  # same as above
assert x.related_part() == SetPart([[0, 1, 2, 3], [4, 5, 6, 9]], 'Z')  # domain Z rather than implicit N
assert x.number_of_related_blocks() == 2
assert x.length() == 10
assert x.affected_elements() == [0, 1, 2, 3, 4, 5, 6, 9]
assert x.number_of_affected_elements() == 8

set equal and complement

set_equal(a, b) merges the blocks containing the elements a and b. set_comp(a, b) makes them complementary.

example

This example shows how an object is changed with the set_equal and set_comp methods.

In the image blocks are marked with black borders, and complementary blocks are connected by (solid) red lines.

The changes are marked with dotted lines. The thick ones are the change explicitly demanded.
The thin dotted lines are changes that implicitly follow. (This is because the complement of a complement must be equal.)
E.g. set_comp(11, 20) is shown as a thick dotted red line between the singleton 11 and the block containing 20.
But the singletons 10 and 11 are already complements, and therefore the 10 must be merged into the block containing 20.
This is marked by the thin dotted green line.

spc = SetPartComp(
    [[3, 4], [5, 6, 7], [8, 9], [20, 30]],
    {(1, 2), (3, 8), (10, 11)}
)
spc.set_equal(2, 4)
assert spc == SetPartComp(
    [[1, 8, 9], [2, 3, 4], [5, 6, 7], [20, 30]],
    {(1, 2), (10, 11)}
)
spc.set_comp(11, 20)
assert spc == SetPartComp(
    [[1, 8, 9], [2, 3, 4], [5, 6, 7], [10, 20, 30]],
    {(1, 2), (10, 11)}
)
spc.set_comp(12, 30)
assert spc == SetPartComp(
    [[1, 8, 9], [2, 3, 4], [5, 6, 7], [10, 20, 30], [11, 12]],
    {(1, 2), (10, 11)}
)
spc.set_equal(6, 13)
assert spc == SetPartComp(
    [[1, 8, 9], [2, 3, 4], [5, 6, 7, 13], [10, 20, 30], [11, 12]],
    {(1, 2), (10, 11)}
)
spc.set_comp(3, 30)
assert spc == SetPartComp(
    [[1, 8, 9, 10, 20, 30], [2, 3, 4, 11, 12], [5, 6, 7, 13]],
    {(1, 2)}
)
spc.set_comp(40, 50)
assert spc == SetPartComp(
    [[1, 8, 9, 10, 20, 30], [2, 3, 4, 11, 12], [5, 6, 7, 13]],
    {(1, 2), (40, 50)}
)
spc.set_equal(60, 70)
assert spc == SetPartComp(
    [[1, 8, 9, 10, 20, 30], [2, 3, 4, 11, 12], [5, 6, 7, 13], [60, 70]],
    {(1, 2), (40, 50)}
)
spc.set_comp(0, 70)
assert spc == SetPartComp(
    [[1, 8, 9, 10, 20, 30], [2, 3, 4, 11, 12], [5, 6, 7, 13], [60, 70]],
    {(1, 2), (40, 50), (0, 60)}
)
spc.set_comp(0, 40)
assert spc == SetPartComp(
    [[0, 50], [1, 8, 9, 10, 20, 30], [2, 3, 4, 11, 12], [5, 6, 7, 13], [40, 60, 70]],
    {(1, 2), (0, 40)}
)
spc.set_equal(0, 1)
assert spc == SetPartComp(
    [[0, 1, 8, 9, 10, 20, 30, 50], [2, 3, 4, 11, 12, 40, 60, 70], [5, 6, 7, 13]],
    {(0, 2)}
)
spc.set_equal(2, 5)
assert spc == SetPartComp(
    [[0, 1, 8, 9, 10, 20, 30, 50], [2, 3, 4, 5, 6, 7, 11, 12, 13, 40, 60, 70]],
    {(0, 2)}
)

all complement pairs

example

x = SetPartComp([[0, 1], [2, 3], [4, 5]], {(0, 2)})
assert x.all_complement_pairs() == {(0, 2), (1, 2), (0, 3), (1, 3)}

x.set_comp(6, 9)
assert x == SetPartComp([[0, 1], [2, 3], [4, 5]], {(0, 2), (6, 9)})
assert x.all_complement_pairs() == {
    (0, 2), (1, 2), (0, 3), (1, 3),
    (6, 9), 
}

x.set_equal(5, 6)
assert x == SetPartComp([[0, 1], [2, 3], [4, 5, 6]], {(4, 9), (0, 2)})
assert x.all_complement_pairs() == {
    (0, 2), (1, 2), (0, 3), (1, 3),
    (4, 9), (5, 9), (6, 9)
}

Boolean function

The method boolf returns a Boolean function (Boolf), which contains the same information.
It is only blight. (Its blightless_boolf is the tautology.)
If there are no gaps between the affected elements x.boolf().blight is equal to x.

from discretehelpers.boolf import Boolf


x = SetPartComp([[0, 1], [2, 3], [4, 5]], {(0, 2)})
assert x.boolf() == Boolf(fullspots=[3, 12, 51, 60], arity=6)
assert x.affected_elements() == x.boolf().atomvals == [0, 1, 2, 3, 4, 5]

assert x == x.boolf().blight

with gaps

There is a gap between 3 and 10. But the blight of a Boolf is always a SetPartComp without gaps.
(There is nothing wrong with this. But it could be a source of confusion.)

x = SetPartComp([[0, 1], [2, 3], [10, 11]], {(0, 2)})
assert x.boolf() == Boolf(fullspots=[3, 12, 51, 60], atomvals=[0, 1, 2, 3, 10, 11])
assert x.affected_elements() == x.boolf().atomvals == [0, 1, 2, 3, 10, 11]

assert x != x.boolf().blight
assert x.boolf().blight == SetPartComp([[0, 1], [2, 3], [4, 5]], {(0, 2)})

integer matches

x.int_matches(n) checks if the binary digits of n are equal or different in the way described by x.
(This is used for the method bloatless_spotint of Boolf.)

example

equal_list = [0, 3, 4, 7, 8, 11, 12, 15]  # The two least-significant binary digits are equal.
diff_list = [1, 2, 5, 6, 9, 10, 13, 14]   # The two least-significant binary digits are different.

equal_spc = SetPartComp([[0, 1]])
diff_spc = SetPartComp([], {(0, 1)})

for n in equal_list:
    assert equal_spc.int_matches(n)
    assert not diff_spc.int_matches(n)

for n in diff_list:
    assert diff_spc.int_matches(n)
    assert not equal_spc.int_matches(n)