Kodeclik Blog
Ordered Sets in Python
An ordered set is just like a set in that it disallows duplicates but it maintains the order of elements. Learn how to implement ordered sets in Python!
There are three ways to implement ordered sets in Python.
Method 1: Use a dictionary
A dictionary comes by default in Python. A dictionary is a sequence of (key, value) pairs. It preserves order and the keys of the dictionary are required to be unique (just like a set). Thus a simple way to implement an ordered set is to use a dictionary data structure and use the keys to represent the elements of the set (the values are irrelevant and we can agree to make them all some same value, e.g., the empty set).
Consider, for instance, the ordered set {‘Hello”, “Kodeclik”, “World”}. Here is Python code to implement this ordered set.
orderedset = {"Hello": {}, "Kodeclik": {}, "World": {}}
print(orderedset)This program prints:
{'Hello': {}, 'Kodeclik': {}, 'World': {}}Note that the order is preserved. To confirm that this works like a set, let us add one more element with the same key:
orderedset = {"Hello": {}, "Kodeclik": {}, "World": {}, "World": {}}
print(orderedset)This again prints:
{'Hello': {}, 'Kodeclik': {}, 'World': {}}To confirm that the ordered set preserves order, let us add a new element to the beginning of the description:
orderedset = {"Mighty": {}, "Hello": {}, "Kodeclik": {},
"World": {}, "World": {}}
print(orderedset)The output is as expected:
{'Mighty': {}, 'Hello': {}, 'Kodeclik': {}, 'World': {}}Method 2: Use a list data structure
The second approach to create an ordered set is to use a list. Recall that a list preserves order which is good for our purposes. However, it allows duplicates which is undesirable for our purposes here. Thus everytime we create the list we must manually check for duplicates and remove them.
Below is such a function to create an ordered set. It takes a list as input and calls a duplicate removal function.
def remove_dups(l):
if (len(l) == 0 or len(l) == 1):
return (l)
elif (l[-1] in l[:-1]):
return(remove_dups(l[:-1]))
else:
newl = remove_dups(l[:-1])
newl.append(l[-1])
return(newl)
def create_ordered_set(l):
return(remove_dups(l))The function remove_dups is written recursively. It takes a single argument as input, which is a list called “l”. If the list is of length 0 or 1, then there can be no duplicates so the function merely returns the list without any modification. If the list is longer (e.g., length 2 or more), then it firsts check if the last element of the list (denoted by l[-1]) is a part of the rest of the list. (If you are not sure of the negative index notation, learn what the -1 index means in Python.) If so, it recursively calls the function on the “rest of the list” and returns it. If it is NOT part of the list, then it still calls the function recursively on the “rest of the list” and then appends that last element (because recall it is not part of the remaining part of the list and so should not be removed).
The function “create_ordered_set” simply calls the “remove_dups” function. You might wonder why do we need one more function but it is often good to be explicit in our definitions. For instance, you might want to use the “remove_dups” function in a different function and not just to create ordered sets always.
You invoke this function like so:
myset = create_ordered_set([1,2,3,2,1])
print(myset)The output of this code will be:
[1, 2, 3]as desired.
Method 3: Use the OrderedSet Class
The primary disadvantage of the above two methods is that while you can create ordered sets you are unable to do other set theoretic operations on the constructed sets, such as set union, intersection, and difference.
Python has an OrderedSet class as part of the “ordered-set” package that you must first install like so:
pip install ordered-setIf successful this should yield a message like:
Installing collected packages: ordered-set
Successfully installed ordered-set-4.1.0Now you can use the OrderedSet class like so:
from ordered_set import OrderedSet
myset = OrderedSet([1,2,1,3,2])
print(myset)
The output will be:
OrderedSet([1, 2, 3])Note that the order is preserved and duplicates are removed as well.
If you attempt to add an element that already exists using the add() method, eg;
from ordered_set import OrderedSet
myset = OrderedSet([1,2,1,3,2])
print(myset)
myset.add(1)
print(myset)
myset.add(0.5)
print(myset)The output will be:
OrderedSet([1, 2, 3])
OrderedSet([1, 2, 3])
OrderedSet([1, 2, 3, 0.5])Note that the first addition does not succeed because you will be adding a duplicate element. The second element succeeds and the order is preserved as well.
In addition, you can perform union, intersection, and difference operations. These operations are implemented using the symbols “|”, “&”, and “-” respectively. Consider:
from ordered_set import OrderedSet
set1 = OrderedSet([1,2,1,3,2])
set2 = OrderedSet([2,3,4,3])
print("Original set 1 = ",set1)
print("Original set 2 = ",set2)
print("Original set 1 Union 2 = ",set1 | set2)
print("Original set 1 Intersection 2 = ",set1 & set2)
print("Original set 1 - 2 = ",set1 - set2)
print("Original set 2 - 1 = ",set2 - set1)The output will be:
Original set 1 = OrderedSet([1, 2, 3])
Original set 2 = OrderedSet([2, 3, 4])
Original set 1 Union 2 = OrderedSet([1, 2, 3, 4])
Original set 1 Intersection 2 = OrderedSet([2, 3])
Original set 1 - 2 = OrderedSet([1])
Original set 2 - 1 = OrderedSet([4])We have seen three methods to implement Python ordered sets; which one is your favorite? The last method is most powerful but does not come standard in Python.
If you liked this blogpost, checkout our post on Python sets (not necessarily ordered). Also closely related to this blogpost is operations such as appending to a Python dictionary.
Interested in more things Python? See our blogpost on Python's enumerate() capability. Also if you like Python+math content, see our blogpost on Magic Squares. Finally, master the Python print function!
Want to learn Python with us? Sign up for 1:1 or small group classes.
