Skip to content

Latest commit

 

History

History
215 lines (182 loc) · 5.09 KB

sets.md

File metadata and controls

215 lines (182 loc) · 5.09 KB

Sets

Introduction

  • A set is an unordered collection data type with no duplicate elements. Sets are iterable and mutable. The elements appear in an arbitrary order when sets are iterated.

  • Sets are commonly used for membership testing, removing duplicates entries, and also for operations such as intersection, union, and set difference.

Creating a set

  • To create an empty set, set1 = set( )
  • To create a set with a string, set2 = set("Baz")

set1 = {'b', 'a', 'z'}

  • If we create a set with repeated elements: set3=set([1,2,3,2,3,1])

set3 = {1,2,3}

Functions :

add()

  • Used to add an element to a set.
  • Complexity: O(1)
set1 = set([1,2,3,4,5])
set1.add(6)
print(s1)

Output:

{1, 2 , 3, 4 ,5 ,6}
  • Similarly, we can add a tuple
set1 = set([1,2,3,4,5])
set1.add((6,7))
print(s1)

Output:

{1, 2, 3, 4, 5 ,(6, 7)}

update()

  • adds elements to set; it is an in-place set union operation
  • Complexity: O(len(s)+len(t)), where s is the set and t is the iterable to be added.
set1 = set([1,2,3,4])
set1.update([5,6])
print(set1)
set1.update({7,8})
print(set1)

Output:

{1,2,3,4,5,6}
{1,2,3,4,5,6,7,8}

discard() and remove()

  • Both are used to remove an element from the set.

  • Both discard and remove take a single argument, the element to be deleted from the set. If the value is not present, discard() does not do anything. Whereas, remove will raise a KeyError exception.

  • Complexity: O(1)

set1 = set([1,2,3,4,5,6,7])
set1.discard(7)
print(set1)
set1.remove(6)
print(s1)
set1.discard(8)
print(set1)
set1.remove(8)

Output:

{1,2,3,4,5,6}
{1,2,3,4,5}
{1,2,3,4,5}
 Traceback (most recent call last):

   File "python", line 1, in <module>
KeyError: 8

copy()

  • Creates a new set with same elements as original one.
  • Complexity: O(n)
set1 = set([1,2,3,4])
set2 = set1.copy()
print(set2)

Output:

{1,2,3,4}

Using assignment here instead of copy() will create a pointer to the already existing set.

clear()

  • Removes all elements from the set.
set1 = set([1,2,3,4])
set1.clear()
print(set1)

Output: { }

pop()

  • Removes and returns arbitrary set element.

  • Raises KeyError exception if set is empty.

  • Complexity: O(1)

set1 = set([1])
set1.pop() #3
set1.pop() # KeyError: 'pop from an empty set'

difference, intersection, union

  • intersection() returns a new set with the elements common in both the sets.

  • union() returns new set with all elements from both the sets.

  • difference() returns a new set with all items from first set not in second.

set1 = {1,2,3,4}
set2 = {3,4,5,6}
print(set1.union(set2))
print(set1.intersection(set2))
print(set1.difference(set2))

Output:

{1,2,3,4,5,6}
{3,4}
{1,2}

isdisjoint, issubset, issuperset

  • isdisjoint() returns true if intersection of sets is empty otherwise false.

  • issubset() returns true if setA is subset of setB, False if not. <= operator can also be used to test for issubset. To check for proper subset < is used. That is set1 < set2 would check if set1 is a proper subset of set 2

set1 = {1,2,3,4}
set2 = {1,2,3,4,5,6}
print(set1.isdisjoint(set2))
print(set1.issubset(set2))
print(set2.issuperset(set1))

Output:

False
True
True

symmetric_difference()

  • Returns a set with all the elements that are in the set and the iterable but not both.
s = set("Hello")
p = set("World")
print s.symmetric_difference(p)

Output:

{'H','e','W','r','d'}

sorting a set

  • Returns a list with elemnts of s in sorted order.
  • Complexity O(nlogn)
s = set([3,2,1,5,7,6,4])
print(sorted(s))

Output:

[1,2,3,4,5,6,7]
  • Note that this returns a list and not a set because sets are not ordered, that is, {2,1} and {1,2} are the same sets.

One example where sets might be used is when we want to count the number of distinct numbers in a given list.

l = [1,2,5,4,2,3,1,5]
s=set(l)
print(len(l)) #number of distinct elements

Output:

5