Exercises with sets

Exercise - syllabs

Write a function syllabs which given a string word made by only bisyllabs and a set found, finds all the distinct bisyllabs and puts them into the set found.

• NOTE: the function syllabs return NOTHING !

Show code cell content Hide code cell content

def syllabs(word, t):
    for i in range(0, len(word), 2):
        t.add(word[i : i + 2])

found = set()
syllabs("banana", found)
print(found)

found = set()
syllabs("parariraparara", found)
print(found)

{'na', 'ba'}
{'ra', 'ri', 'pa'}

Exercise - distinguish

✪✪ Write a function distinguish which given a list big_list containing sublists of two characters each, RETURN a NEW LIST containing all the distinct sublists (ignoring the duplicated sublists)

• the returned list must have the elements in the same order in which they were found in big_list

• variable big_list must not be modified

• to know fast whether a sublist was already found, use a set

• DO NOT search in lists (so no count, index, in in lists - they’re slow!)

• DO NOT remove from lists (so no remove from lists - it’s slow!)

• HINT: lists are mutable, can we place them in a set? If it’s not possible, what can we do?

Show code cell content Hide code cell content

def distinguish(blist):
    s = set()
    ret = []
    
    for sublist in blist: 
        #  In sets we can't place lists because they are mutable, 
        #  but we can insert tuples        
        tup = tuple(sublist)

        #  Checking whether an element belongs to a set it's very fast:
        #  it is independent from the set dimension!    
        
        if tup not in s:  
            ret.append(sublist)
            # Adding an element to a set is very fast:
            # it is independent from the set dimension!            
            s.add(tup)
    
    return ret    

big_list = [
    ["d", "d"],
    ["a", "b"],
    ["d", "d"],
    ["c", "a"],
    ["c", "a"],
    ["d", "d"],
    ["a", "b"],
]
print("distincts:", distinguish(big_list))
print("big_list:", big_list)

distincts: [['d', 'd'], ['a', 'b'], ['c', 'a']]
big_list: [['d', 'd'], ['a', 'b'], ['d', 'd'], ['c', 'a'], ['c', 'a'], ['d', 'd'], ['a', 'b']]

Exercise - intersectron

Given a list sets containing an arbitrary number of sets, RETURN a NEW set which contains the elements common to all sets.

To solve the exercise, you can intersecate a set at a time with a for cycle (slow) or with the technique described here (short and fast).

• try to solve it in both ways

• BEWARE of the empty list!

• your code must work with any number of sets (the image is just an example)

Show code cell content Hide code cell content

def inter_for(sets):
    if len(sets) == 0:
        return set()

    first = True

    for el in sets:
        if first:
            ret = set(el)
            first = False
        else:
            ret.intersection_update(el)
    return ret

assert inter_for([]) == set()
assert inter_for([set(), set()]) == set()
assert inter_for([set(), set(), set()]) == set()
assert inter_for([{"a"}, {"a"}, {"a"}]) == {"a"}
assert inter_for([{"a", "b"}, {"b"}, {"b"}]) == {"b"}
assert inter_for([{"a"}, {"a", "b"}, {"a"}]) == {"a"}
assert inter_for([{"c"}, {"c"}, {"c", "b"}]) == {"c"}
assert inter_for([{"a", "b"}, {"a", "b"}, {"a", "b"}]) == {"a", "b"}
assert inter_for(
    [{"a", "b", "c"}, {"a", "b", "c", "d"}, {"b", "c", "d"}, {"b", "c"}]
) == {"b", "c"}

# check we didn't modify the input sets
s = {"a", "b"}
assert inter_for([s, {"b", "c"}]) == {"b"}
assert s == {"a", "b"}

Show code cell content Hide code cell content

def inter_fast(sets):
    if len(sets) == 0:
        return set()
    
    return set.intersection(*sets)

assert inter_fast([]) == set()
assert inter_fast([set(),set()]) == set()
assert inter_fast([set(),set(),set()]) == set()
assert inter_fast([{'a'},{'a'},{'a'}]) == {'a'}
assert inter_fast([{'a','b'},{'b'},{'b'}]) == {'b'}
assert inter_fast([{'a'},{'a','b'},{'a'}]) == {'a'}
assert inter_fast([{'c'},{'c'},{'c','b'}]) == {'c'}
assert inter_fast([{'a','b'},{'a','b'},{'a','b'}]) == {'a','b'}
assert inter_fast([{'a','b','c'},{'a','b','c','d'},{'b','c','d'}, {'b','c'}]) == {'b','c'}

# check we didn't modify the input sets
s = {'a','b'}
assert inter_fast([s,{'b','c'}]) == {'b'}
assert s == {'a','b'}