Sets

The galactic.algebras.set module defines several set classes.

FrozenFIFOSet for creating frozen FIFO sets;
FIFOSet for creating FIFO sets;
IntegerSet for creating compact sets of integers;
FiniteUniverse for creating finite universes;
FiniteSubSet for creating subset of finite universes;

class FrozenFIFOSet(*args)

Bases: Set[_T]

It represents frozen sets that keep the FIFO order.

Initialise an instance using 0 or 1 argument that should be iterable.

Parameters:

*args (Iterable[TypeVar(_T)]) – An iterable.

Raises:

TypeError – If two or more arguments are given.
TypeError – If the argument is not iterable.

Examples

>>> from galactic.algebras.set import FrozenFIFOSet
>>> a = FrozenFIFOSet[int]([3, 5, 1, 2, 6, 2])
>>> list(a)
[3, 5, 1, 2, 6]
>>> list(a | FrozenFIFOSet[int]([1, 5, 7 ,8, 9]))
[3, 5, 1, 2, 6, 7, 8, 9]

copy()

Compute a copy of this set.

Return type:: Self
Returns:: A copy of this set.

property head: _T

Return the first value of the set.

Return type:: The first value.
Raises:: KeyError – If the set is empty.

property tail: _T

Return the last value of the set.

Return type:: The last value.
Raises:: KeyError – If the set is empty.

isdisjoint(other)

Test if the set is disjoint from the other.

Parameters:: other (Iterable[Any]) – An iterable of elements.
Returns:: True if the set is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the set is in other.

Parameters:: other (Iterable[Any]) – An iterable of elements.
Returns:: True if the set is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other set is in the set.

Parameters:: other (Iterable[Any]) – An iterable of elements.
Returns:: True if the set is a superset of the other.
Return type:: bool

union(*others)

Compute the union of the set and the others.

Parameters:: *others (Iterable[TypeVar(_T)]) – A sequence of iterable.
Returns:: The union of the set and the others.
Return type:: Self

intersection(*others)

Compute the intersection between the set and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The intersection between the set and the others
Return type:: Self

difference(*others)

Compute the difference between the set and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The difference between the set and the others
Return type:: Self

symmetric_difference(other)

Compute the symmetric difference between the set and the other.

Parameters:: other (Iterable[TypeVar(_T)]) – An iterable of elements.
Returns:: The symmetric difference between the set and the other.
Return type:: Self

class FIFOSet(*args)

Bases: FrozenFIFOSet[_T], MutableSet[_T]

it represents mutable sets that keep the FIFO order.

Examples

>>> from galactic.algebras.set import FIFOSet
>>> a = FIFOSet[int]([3, 5, 1, 2, 6, 2])
>>> list(a)
[3, 5, 1, 2, 6]
>>> list(a | FIFOSet[int]([1, 5, 7 ,8, 9]))
[3, 5, 1, 2, 6, 7, 8, 9]

add(value)

Add the value to the set.

Parameters:: value (TypeVar(_T)) – The value to add.
Return type:: None

remove(value)

Remove value from the set if it is present.

Parameters:: value (TypeVar(_T)) – The value to remove.
Return type:: None

discard(value)

Discard value from the set if it is present.

Parameters:: value (TypeVar(_T)) – The value to remove.
Return type:: None

pop()

Remove and return the first value of the set.

Return type:: TypeVar(_T)
Returns:: The value removed.

clear()

Clear the set.

Return type:: None

update(*others)

Update a set with the union of itself and others.

Parameters:: *others (Iterable[TypeVar(_T)]) – A sequence of iterable.
Return type:: None

intersection_update(*others)

Update a set with the intersection of itself and others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Return type:: None

difference_update(*others)

Update a set with the difference of itself and others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Return type:: None

symmetric_difference_update(other)

Update a set with the symmetric difference of itself and the other.

Parameters:: other (Iterable[TypeVar(_T)]) – An iterable of elements.
Return type:: None

move_to_end(value, last=True)

Move an existing value to either end of the set.

The value is moved to the right end if last is True (the default) or to the beginning if last is False.

Parameters:

value (TypeVar(_T)) – The value to move
last (bool, default: True) – Where to move

Return type:

None

additem(value, last=True)

Add value to the set either at the beginning or at the end.

Parameters:

value (TypeVar(_T)) – The value to add.
last (bool, default: True) – Where to add.

Return type:

None

popitem(last=False)

Remove and return an existing value from either end of the set.

Parameters:: last (bool, default: False) – Does the remove take place at the end or the beginning?
Returns:: The value removed.
Return type:: _T
Raises:: KeyError – if the set is empty.

class IntegerSet(intervals=None)

Bases: Set[int]

It represents subsets of set of integers.

Parameters:

intervals (Iterable[tuple[int, int]] | None, default: None) – An optional iterable of intervals.

Raises:

ValueError – If the intervals are not sorted.
ValueError – If an interval is empty.
Instances store membership using a compact array of intervals represented by –
an array of int. It uses –
inversion lists <https://en.wikipedia.org/wiki/Inversion_list>`_ as inne –
data structures. –
For example, the {0,1,3,4} subset will be represented by [0,2,3,5] meaning: –
* from element 0 (included) to element 2 (excluded) –
* from element 3 (included) to element 5 (excluded) –

Examples

>>> from galactic.algebras.set import IntegerSet
>>> set1 = IntegerSet([(0, 2), (3, 5)])
>>> list(set1)
[0, 1, 3, 4]
>>> len(set1)
4
>>> 0 in set1
True
>>> 5 in set1
False
>>> set2 = IntegerSet([(1, 2), (3, 6)])
>>> list(set2)
[1, 3, 4, 5]
>>> list(set1 | set2)
[0, 1, 3, 4, 5]
>>> list(set1 & set2)
[1, 3, 4]
>>> list(set1 ^ set2)
[0, 5]
>>> set1 & set2 <= set1
True
>>> set1 | set2 >= set1
True
>>> set1.isdisjoint(set2)
False

classmethod from_iterable(iterable=None)

Create an instance from an iterable.

Parameters:: iterable (Iterable[int] | None, default: None) – An optional iterable of integers.
Returns:: A new set.
Return type:: Self

copy()

Compute a copy of this set.

Return type:: Self
Returns:: A copy of this set.

isdisjoint(other)

Test if the set is disjoint from the other.

Parameters:: other (Iterable[Any]) – An iterable of values.
Returns:: True if the set is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the set is in other.

Parameters:: other (Iterable[Any]) – An iterable of elements.
Returns:: True if the set is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other set is in the set.

Parameters:: other (Iterable[Any]) – An iterable of elements.
Returns:: True if the set is a superset of the other.
Return type:: bool

union(*others)

Compute the union of the set and the others.

Parameters:: *others (Iterable[int]) – A sequence of iterable.
Returns:: The union of the set and the others.
Return type:: Self

intersection(*others)

Compute the intersection between the set and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The intersection between the set and the others
Return type:: Self

difference(*others)

Compute the difference between the set and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The difference between the set and the others
Return type:: Self

symmetric_difference(other)

Compute the symmetric difference between the set and the other.

Parameters:: other (Iterable[int]) – An iterable of elements.
Returns:: The symmetric difference between the set and the other.
Return type:: Self

intervals()

Get an iterator over the intervals.

Return type:: Iterator[tuple[int, int]]
Returns:: An iterator over the intervals.

ranges()

Get an iterator over the ranges.

Return type:: Iterator[range]
Returns:: An iterator over the ranges.

class FiniteUniverse(iterable)

Bases: Set[_T], Sequence[_T]

It represents finite universes.

Parameters:: iterable (Iterable[TypeVar(_T)]) – An iterable of values.

Examples

>>> from galactic.algebras.set import FiniteUniverse
>>> universe = FiniteUniverse[str]("abc")
>>> list(universe)
['a', 'b', 'c']
>>> list(reversed(universe))
['c', 'b', 'a']
>>> universe.index('c')
2
>>> universe.count('c')
1
>>> universe.count('g')
0
>>> list(universe.whole)
['a', 'b', 'c']
>>> [list(singleton) for singleton in universe.singletons()]
[['a'], ['b'], ['c']]
>>> [list(subset) for subset in universe.parts()]
[[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]

index(value, start=None, stop=None)

Get the index of a value.

Parameters:

value (TypeVar(_T)) – The value whose index is requested.
start (int | None, default: None) – Where to start.
stop (int | None, default: None) – Where to stop.

Returns:

The index requested.

Return type:

int

Raises:

ValueError – If the value is not in the universe or not found in the interval.

count(value)

Get the total number of occurrences of value.

Parameters:: value (object) – The value whose count is requested.
Returns:: 1 if the value is in the universe, else 0.
Return type:: int

parts(inf=None, sup=None)

Get an iterator over the parts of this universe.

Parameters:

inf (int | None, default: None) – The lower cardinality of the produced parts.
sup (int | None, default: None) – The upper cardinality of the produced parts.

Returns:

An iterator over the selected parts of this universe

Return type:

Iterator[FiniteSubSet[_T]]

singletons()

Get an iterator over the singletons of this universe.

Return type:: Iterator[FiniteSubSet[TypeVar(_T)]]
Returns:: An iterator over the singletons of this universe

property empty: FiniteSubSet[_T]

Get the empty subset of this universe.

Returns:: The empty subset.
Return type:: FiniteSubSet[_T]

property whole: FiniteSubSet[_T]

Get the whole subset of this universe.

Returns:: The whole subset.
Return type:: FiniteSubSet[_T]

class FiniteSubSet(universe, elements=None)

Bases: Set[_T]

It represents subsets of a finite universe.

Instances stores membership using a compact array of intervals represented by an array of int. For example, using the abcdef universe, the abde subset will be represented by [0,2,3,5] meaning:

from element 0 (included) to element 2 (excluded) of universe
from element 3 (included) to element 5 (excluded) of universe

Parameters:

universe (FiniteUniverse[TypeVar(_T)]) – A finite universe.
elements (Iterable[TypeVar(_T)] | None, default: None) – An optional iterable.

Examples

>>> from galactic.algebras.set import FiniteUniverse, FiniteSubSet
>>> from pprint import pprint
>>> universe = FiniteUniverse[str]("abcdef")
>>> set1 = FiniteSubSet[str].from_intervals(universe, [(0, 2), (3, 5)])
>>> list(set1.universe)
['a', 'b', 'c', 'd', 'e', 'f']
>>> len(set1)
4
>>> "a" in set1
True
>>> "f" in set1
False
>>> list(~set1)
['c', 'f']
>>> set2 = FiniteSubSet[str](universe, "bdef")
>>> list(set2.intervals())
[(1, 2), (3, 6)]
>>> list(set1 | set2)
['a', 'b', 'd', 'e', 'f']
>>> list((set1 | set2).intervals())
[(0, 2), (3, 6)]
>>> list(set1 & set2)
['b', 'd', 'e']
>>> list(set1 ^ set2)
['a', 'f']
>>> set1 & set2 <= set1
True
>>> set1 | set2 >= set1
True
>>> set1.isdisjoint(set2)
False
>>> pprint([list(subset) for subset in set1.subsets()])
[[],
 ['a'],
 ['b'],
 ['d'],
 ['e'],
 ['a', 'b'],
 ['a', 'd'],
 ['a', 'e'],
 ['b', 'd'],
 ['b', 'e'],
 ['d', 'e'],
 ['a', 'b', 'd'],
 ['a', 'b', 'e'],
 ['a', 'd', 'e'],
 ['b', 'd', 'e'],
 ['a', 'b', 'd', 'e']]
>>> pprint([list(superset) for superset in set1.supersets(strict=True)])
[['a', 'b', 'c', 'd', 'e'],
 ['a', 'b', 'd', 'e', 'f'],
 ['a', 'b', 'c', 'd', 'e', 'f']]

copy()

Compute a copy of this set.

Returns:: A copy of this set.
Return type:: Self

classmethod from_intervals(universe, intervals=None)

Create an instance.

Parameters:

universe (FiniteUniverse[TypeVar(_T)]) – A finite universe.
intervals (Iterable[tuple[int, int]] | None, default: None) – An optional iterable of intervals.

Returns:

The new set.

Return type:

Self

Raises:

ValueError – If a mark is outside of the universe.

isdisjoint(other)

Test if the set is disjoint from the other.

Parameters:: other (Iterable[object]) – An iterable of values.
Returns:: True if the set is disjoint from the other.
Return type:: bool

issubset(other)

Test if the set is a subset of the other.

Parameters:: other (Iterable[object]) – An iterable of values.
Returns:: True if the set is a subset of the other.
Return type:: bool

issuperset(other)

Test if the set is a superset of the other.

Parameters:: other (Iterable[object]) – An iterable of values.
Returns:: True if the set is a superset of the other.
Return type:: bool

union(*others)

Compute the union of the set and the others.

Parameters:: *others (Iterable[TypeVar(_T)]) – A sequence of iterable.
Returns:: The union of the set and the others.
Return type:: Self

intersection(*others)

Compute the intersection between the set and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The intersection between the set and the others
Return type:: Self

difference(*others)

Compute the difference between the set and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The difference between the set and the others
Return type:: Self

symmetric_difference(other)

Compute the symmetric difference between the set and the other.

Parameters:: other (Iterable[TypeVar(_T)]) – An iterable of elements.
Returns:: The symmetric difference between the set and the other.
Return type:: Self

intervals()

Get an iterator over the intervals.

Return type:: Iterator[tuple[int, int]]
Returns:: An iterator over the intervals.

ranges()

Get an iterator over the ranges.

Return type:: Iterator[range]
Returns:: An iterator over the ranges.

subsets(strict=None)

Get an iterator over the subset of this set (including itself).

Parameters:: strict (bool | None, default: None) – Are the subsets strict?
Returns:: An iterator over the subsets.
Return type:: Iterator[Self]

supersets(strict=None)

Get an iterator over the supersets of this set (including itself).

Parameters:: strict (bool | None, default: None) – Are the subsets strict?
Returns:: An iterator over the supersets.
Return type:: Iterator[Self]

property universe: FiniteUniverse[_T]

Get the underlying universe.

Returns:: The underlying universe.
Return type:: FiniteUniverse[_T]