A set object is an unordered collection of distinct hashable objects. It’s one of Python’s built-in types and allows the dynamic adding and removing of elements, iteration, and operations with another set objects.
Sets are as fundamental to computer science as they are to mathematics. Sets manipulated by algorithms can grow, shrink, or otherwise change over time, we call such sets dynamic. Data structures present techniques for representing finite dynamic sets and manipulating them on a computer.
The best way to implement a dynamic set depends upon the operations that must be supported.
Can be grouped into two categories:
Queries, which simply return information about the set.
Modifying operations, which change the set.
SEARCH(S,k)
INSERT(S,x)
DELETE(S,x)
Algorithms may require several different types of operations to be performed on sets. For example, many algorithms need only the ability to:
Insert elements into
Delete elements from
Test membership in a set.
We call a dynamic set that supports these operations a dictionary.
Other algorithms require more complicated operations, such as min-priority queues, which support the operation of inserting an element into and extracting the smallest element from a set.
"""
disjoint set
Reference: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
"""
class Node:
def __init__(self, data):
self.data = data
def make_set(x):
"""
make x as a set.
"""
# rank is the distance from x to its' parent
# root's rank is 0
x.rank = 0
x.parent = x
def union_set(x, y):
"""
union two sets.
set with bigger rank should be parent, so that the
disjoint set tree will be more flat.
"""
x, y = find_set(x), find_set(y)
if x.rank > y.rank:
y.parent = x
else:
x.parent = y
if x.rank == y.rank:
y.rank += 1
def find_set(x):
"""
return the parent of x
"""
if x != x.parent:
x.parent = find_set(x.parent)
return x.parent
def find_python_set(node: Node) -> set:
"""
Return a Python Standard Library set that contains i.
"""
sets = ({0, 1, 2}, {3, 4, 5})
for s in sets:
if node.data in s:
return s
raise ValueError(f"{node.data} is not in {sets}")
def test_disjoint_set():
"""
>>> test_disjoint_set()
"""
vertex = [Node(i) for i in range(6)]
for v in vertex:
make_set(v)
union_set(vertex[0], vertex[1])
union_set(vertex[1], vertex[2])
union_set(vertex[3], vertex[4])
union_set(vertex[3], vertex[5])
for node0 in vertex:
for node1 in vertex:
if find_python_set(node0).isdisjoint(find_python_set(node1)):
assert find_set(node0) != find_set(node1)
else:
assert find_set(node0) == find_set(node1)
if __name__ == "__main__":
test_disjoint_set()MINIMUM(S)MAXIMUM(S)
SUCCESSOR(S,x)
PREDECESSOR(S,x)
def main():
set1 = {1, 2, 3, 3, 3, 2}
print(set1)
print('Length =', len(set1))
set2 = set(range(1, 10))
print(set2)
set1.add(4)
set1.add(5)
set2.update([11, 12])
print(set1)
print(set2)
set2.discard(5)
# would rise KeyError if the to-remove element not exist
if 4 in set2:
set2.remove(4)
print(set2)
# for loop all elements in set
for elem in set2:
print(elem ** 2, end=' ')
print()
# transfer tuple to set
set3 = set((1, 2, 3, 3, 2, 1))
print(set3.pop())
print(set3)
### set calculation on union / intersection / difference / ...
print(set1 & set2)
# print(set1.intersection(set2))
print(set1 | set2)
# print(set1.union(set2))
print(set1 - set2)
# print(set1.difference(set2))
print(set1 ^ set2)
# print(set1.symmetric_difference(set2))
# check subset and superset
print(set2 <= set1)
# print(set2.issubset(set1))
print(set3 <= set1)
# print(set3.issubset(set1))
print(set1 >= set2)
# print(set1.issuperset(set2))
print(set1 >= set3)
# print(set1.issuperset(set3))
if __name__ == '__main__':
main()
A set object is an unordered collection of distinct hashable objects. It’s one of Python’s built-in types and allows the dynamic adding and removing of elements, iteration, and operations with another set objects.
ArrayBinary Search TreeLinked ListExtra-ArrayStackBinary TreeRecursionHash TableSearchingSortingQueue SandboxHash TableDouble Linked ListGraphsExoticHeap"""
Sets are an unordered collection of unique values that can be modified at
runtime. This module shows how sets are created, iterated, accessed,
extended and shortened.
"""
def main():
# Let's define one `set` for starters
simple_set = {0, 1, 2}
# A set is dynamic like a `list` and `tuple`
simple_set.add(3)
simple_set.remove(0)
assert simple_set == {1, 2, 3}
# Unlike a `list and `tuple`, it is not an ordered sequence as it
# does not allow duplicates to be added
for _ in range(5):
simple_set.add(0)
simple_set.add(4)
assert simple_set == {0, 1, 2, 3, 4}
# Now let's define two new `set` collections
multiples_two = set()
multiples_four = set()
# Fill sensible values into the set using `add`
for i in range(10):
multiples_two.add(i * 2)
multiples_four.add(i * 4)
# As we can see, both sets have similarities and differences
assert multiples_two == {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}
assert multiples_four == {0, 4, 8, 12, 16, 20, 24, 28, 32, 36}
# We cannot decide in which order the numbers come out - so let's
# look for fundamental truths instead, such as divisibility against
# 2 and 4. We do this by checking whether the modulus of 2 and 4
# yields 0 (i.e. no remainder from performing a division)
multiples_common = multiples_two.intersection(multiples_four)
for number in multiples_common:
assert number % 2 == 0 and number % 4 == 0
# We can compute exclusive multiples
multiples_two_exclusive = multiples_two.difference(multiples_four)
multiples_four_exclusive = multiples_four.difference(multiples_two)
assert len(multiples_two_exclusive) > 0
assert len(multiples_four_exclusive) > 0
# Numbers in this bracket are greater than 2 * 9 and less than 4 * 10
for number in multiples_four_exclusive:
assert 18 < number < 40
# By computing a set union against the two sets, we have all integers
# in this program
multiples_all = multiples_two.union(multiples_four)
# Check if set A is a subset of set B
assert multiples_four_exclusive.issubset(multiples_four)
assert multiples_four.issubset(multiples_all)
# Check if set A is a subset and superset of itself
assert multiples_all.issubset(multiples_all)
assert multiples_all.issuperset(multiples_all)
# Check if set A is a superset of set B
assert multiples_all.issuperset(multiples_two)
assert multiples_two.issuperset(multiples_two_exclusive)
if __name__ == "__main__":
main()