Disjoint Sets – Python

Disjoint sets are a fundamental concept in set theory. In mathematics, disjoint sets are defined as sets (collections of elements) that have no elements in common. In other words, two sets A and B are disjoint if their intersection is an empty set => A ∩ B = ∅

Disjoint Sets

Key Points of Disjoint Sets:

• Two sets A and B can be disjoint sets, when there is no element common between these two sets. i.e if there is not a single element x such that x ∈ A and x ∈ B. It means intersection of two sets A and B should be empty.
• Mutual Exclusivity: Disjoint sets are mutually exclusive. It means, if an object x is an element of Set A, then simultaneously it cannot be an element of Set B also.

Example of Disjoint Sets

Properties of Disjoint Sets

1. Disjoint set follows commutativity property. Commutative means, If Set A is disjoint from Set B, then Set B is disjoint from set A. i.e. if A ∩ B = ∅, then B ∩ A = ∅.
2. Union of two disjoint sets A and B will be a resultant set that contains all elements of both Set A and Set B without duplication. i.e. A ∪ B = { x ∣ x ∈ A or x ∈ B }
3. Cardinality of a set is number of elements in that set. If Set A and Set B have finite number of elements and are disjoint sets, then cardinality (number of elements) of the Union of these sets is the sum of their cardinalities. i.e number of elements in Union of Set A and Set B will be equal to sum of number of elements in Set A and Set B. => ∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣

Python provides built-in method isdisjoint() to check if the sets are disjoint or not. Lets see, how isdisjoint() method can be used in different ways.

Using isdisjoint() method

• Syntax – set_1.isdisjoint(set_2)
• isdisjoint() method takes a single “iterable” as an argument.
• isdisjoint() method returns boolean (True or False) value. True means sets are disjoint sets and False sets are not disjoint sets.

# check set has common elements - using isdisjoint() method
print("check set has common elements - using isdisjoint() method")
set_1 = {10, 20, 30}
set_2 = {70, 80, 90}
set_3 = {10, 20, 30, 70, 80, 90}

isdisjoint_set12 = set_1.isdisjoint(set_2)           # check set_1 is disjoint set with set_2
isdisjoint_set21 = set_2.isdisjoint(set_1)           # check set_2 is disjoint set with set_1

print(set_1)
print(set_2)
print(isdisjoint_set12)               # return value for set_1 is disjoint set with set_2
print(isdisjoint_set21)               # return value for set_2 is disjoint set with set_1

print(set_3)
isdisjoint_set13 = set_1.isdisjoint(set_3)            # check set_1 is disjoint set with set_3
print(isdisjoint_set13)              # return value for set_1 is disjoint set with set_3

We have defined three sets referenced by variables set_1, set_2 and set_3. Using built-in isdisjoint() method we are checking if set_1 and set_2 are disjoint to each other or not. We are also checking for disjoint between set_1 and set_3. Output from isdisjoint() method will be a boolean value.

Program Output

check set has common elements - using isdisjoint() method
{10, 20, 30}             # elements of set_1
{80, 90, 70}             # elements of set_2
True                         # set_1 disjoint to set_2
True                         # set_2 disjoint to set_1
{80, 20, 90, 70, 10, 30}          # elements of set_3
False                        # set_1 is not disjoint to set_3

From the program output, set_1, set_2 and set_3 elements are printed. isdisjoint() method has return a boolean (True or False) value. set_1 and set_2 are disjoint to each other. But there are common elements in set_1 and set_3, so they are not disjoint (False).

Using isdisjoint() method – with empty sets

• Syntax – set_1.isdisjoint(set_2)

# using isdisjoint() method - with empty sets
print("using isdisjoint() method - with empty sets")

set_1 = set()
set_2 = set()
empty_isdisjoint = set_1.isdisjoint(set_2)         # check set_1 is disjoint set with set_2

print(set_1)
print(set_2)
print(empty_isdisjoint)               # return value for set_1 is disjoint set with set_2

We have defined two sets referenced by variables set_1 and set_2. Both sets are empty sets. Using built-in isdisjoint() method we are checking if set_1 and set_2 are disjoint to each other or not. Output from isdisjoint() method will be a boolean value.

Program Output

using isdisjoint() method - with empty sets
set()
set()
True           # set_1 is disjoint to set_2

Since both sets set_1 and set_2 are empty sets, there will not be any common element between them i.e. A ∩ B = ∅. So, these two sets are disjoint sets.

Using isdisjoint() method – with set and dictionary

• Syntax – set_1.isdisjoint(dict_1)
• isdisjoint() method takes a single “iterable” as an argument.

When we are using Dictionary collection with isdisjoint() method then internally, Set of dictionary keys is compared for disjoint or not. For example:

set_1 = {10, 20, 30}
dict_1 = {1: "aaa", 2: "bbb", 3: "ccc"}, then its keys set will be
dict_keys_set = {1, 2, 3} i.e. this set will be checked for disjoint with the given set.
=> set_1.isdisjoint(dict_1) => {10, 20, 30}.isdisjoint({1, 2, 3})

# using isdisjoint() method - with set and dictionary
print("using isdisjoint() method - with set and dictionary")

set_1 = {"a", "b", "c"}
dict_1 = {"a": "Python", "b": "NumPy", "c": "PowerBI"}
dict_2 = {"Python": "a", "NumPy": "b", "PowerBI": "c"}

isdisjoint_set1_dict1 = set_1.isdisjoint(dict_1)    # dict_1 keys set => {"a", "b", "c"}
isdisjoint_set1_dict2 = set_1.isdisjoint(dict_2)    # dict_2 keys set => {"Python", "NumPy", "PowerBI"}

print(set_1)
print(dict_1)
print(dict_2)
print(isdisjoint_set1_dict1)          # check set_1 is disjoint set with dict_1 keys set
print(isdisjoint_set1_dict2)          # check set_1 is disjoint set with dict_2 keys set

We have defined one set referenced by variable set_1 and two dictionaries dict_1 and dict_2. Using built-in isdisjoint() method we are checking if set_1 and dict_1 are disjoint to each other or not. We are also checking for disjoint between set_1 and dict_2. Output from isdisjoint() method will be a boolean value.

Program Output

using isdisjoint() method - with set and dictionary
{'a', 'b', 'c'}              #  elements of set_1
{'a': 'Python', 'b': 'NumPy', 'c': 'PowerBI'}         # elements of dict_1
{'Python': 'a', 'NumPy': 'b', 'PowerBI': 'c'}         # elements of dict_2

False         # set_1 is not disjoint to dict_1
True           # set_1 is disjoint to dict_2

From the program output, set_1 , dict_1 and dict_2 elements are printed. isdisjoint() method has return a boolean False value for set_1 & dict_1 and True for set_1 and dict_2.

Custom implementation – isdisjoint() method

Internally in Python, isdisjoint() method checks for any common elements between the given two sets. If no common elements are found between the sets, method returns True; otherwise, it returns False.

Lets see the custom code to implement functioning of isdisjoint() method.

def custom_isdisjoint(set2):
    # Iterate through elements of set1
    for element in set1:
        # Check if any element of set1 is in set2
        if element in set2:
            return False
    return True

set1 = {10, 20, 30}
set2 = {40, 50, 60}
set3 = {30, 40, 50}

print(custom_isdisjoint(set1, set2))  # Output: True
print(custom_isdisjoint(set1, set3))  # Output: False

• custom_isdisjoint() function iterates through each element in set1.
• For each element in set1, it checks if the element is present in set2.
• If any element is found in both sets, the function returns False, else it will continue to check for all the elements of set1. If no common elements are found by the end of iteration for set1, it will return True.

Summary

In this article we learn about various disjoint operation on Sets. Following scenarios were explored:

• Disjoint Sets
  • Properties of Disjoint Sets
  • Using isdisjoint() method
  • Using isdisjoint() method – with empty sets
  • Using isdisjoint() method – with set and dictionary
  • Custom implementation – isdisjoint() method

Code – Github Repository

All code snippets and programs for this article and for Python tutorial, can be accessed from Github repository – Comments and Docstring in Python.

Interview Questions & Answers

Q: How does the isdisjoint() method work?

isdisjoint() method iterates over the elements of the set on which it’s called and checks if any element exists in the other set (passed as an argument). If it finds any common element, it immediately returns False. If no common elements are found after iterating through the set, it returns True.

Q: What is the time complexity of the isdisjoint() method?

Time complexity of the isdisjoint() method is O(min(len(set1), len(set2))). It iterates over the smaller set to checks for common elements between the two sets. Comparing value in the larger set can take O(1) time because sets uses hashtable structure internally.

Q: Can we use the isdisjoint() method with other data types like list or tuple?

isdisjoint() method can be used with other iterable types, such as lists, tuples, or dictionaries, but method should be called on a set. When the method is used, the iterable passed as an argument is converted to a set for the disjoint check.

set_1 = {10, 20, 30}
list_1 = [40, 50, 60]
print(set_1.isdisjoint(list_1))  # True

Q: Real-world scenario where isdisjoint() might be useful?

Common use case of isdisjoint() method is in implementation of role-based access control (RBAC) system, where we need to ensure that no user is assigned roles that conflict with each other.

Q: Is it possible to use isdisjoint() with a frozenset?

Yes, isdisjoint() method can be used with a frozenset. A frozenset is an immutable version of a set and supports all the set operations, including isdisjoint().

set_1 = {10, 20, 30}
frozen_set = frozenset([40, 50, 60])
print(set_1.isdisjoint(frozen_set))  # True
print(frozen_set.isdisjoint(set_1))  # True

• set_1.isdisjoint(frozen_set) – We are using isdisjoint() method on set and passing frozenset as an argument.
• frozen_set.isdisjoint(set_1) – We are using isdisjoint() method on frozenset and passing set as an argument.

Q: Can can we calculate isdisjoint() with multiple sets?

list_of_sets = [{13, 23}, {35, 46}, {57, 68}]
all_disjoint = True

for index in range(len(list_of_sets)):
    for j in range(index + 1, len(list_of_sets)):
        if not list_of_sets[index].isdisjoint(list_of_sets[j]):
            all_disjoint = False
            break

print(all_disjoint)  # True

1. We have defined a list list_of_sets, contains all elements as set. We have to check for isdisjoint() between these sets.
2. Using for loop and range() method, we are iterating over the index of the list, it will start from index 0.
3. Using another for loop, which will start from next index position (from index 1 when index is 0 in parent) and iterate over the entire list.
4. We will check if the two sets are isdisjoint() or not.
5. If two sets are not disjoint, then all_disjoint variable will be set to False and break the for loop.
6. If two sets are disjoint, then it will take the next set from list and will check for disjoint between these two sets.
7. Similarly it will iterate and compare all the sets with each other.
8. Finally if all sets are disjoint, then will return True.