CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Sets and Maps: Worked Examples


  1. isPermutation(L)
  2. repeats(L)
  3. mostFrequent(L)
  4. isAnagram(s1, s2)

  1. isPermutation(L)
    def isPermutation(L):
        # return True if L is a permutation of [0,...,n-1]
        # and False otherwise
        return (set(L) == set(range(len(L))))
    
    def testIsPermutation():
        print("Testing isPermutation()...", end="")
        assert(isPermutation([0,2,1,4,3]) == True)
        assert(isPermutation([1,3,0,4,2]) == True)
        assert(isPermutation([1,3,5,4,2]) == False)
        assert(isPermutation([1,4,0,4,2]) == False)
        print("Passed!")
    
    testIsPermutation()

  2. repeats(L)
    def repeats(L):
        # return a sorted list of the repeat elements in the list L
        seen = set()
        seenAgain = set()
        for element in L:
            if (element in seen):
                seenAgain.add(element)
            seen.add(element)
        return sorted(seenAgain)
    
    def testRepeats():
        print("Testing repeats()...", end="")
        assert(repeats([1,2,3,2,1]) == [1,2])
        assert(repeats([1,2,3,2,2,4]) == [2])
        assert(repeats(list(range(100))) == [ ])
        assert(repeats(list(range(100))*5) == list(range(100)))
        print("Passed!")
    
    testRepeats()

  3. mostFrequent(L)
    def mostFrequent(L):
        # Return most frequent element in L, resolving ties arbitrarily.
        maxValue = None
        maxCount = 0
        counts = dict()
        for element in L:
            count = 1 + counts.get(element, 0)
            counts[element] = count
            if (count > maxCount):
                maxCount = count
                maxValue = element
        return maxValue
    
    def testMostFrequent():
        print("Testing mostFrequent()... ", end="")
        assert(mostFrequent([2,5,3,4,6,4,2,4,5]) == 4)
        assert(mostFrequent([2,3,4,3,5,3,6,3,7]) == 3)
        assert(mostFrequent([42]) == 42)
        assert(mostFrequent([]) == None)
        print("Passed!")
    
    testMostFrequent()

  4. isAnagram(s1, s2)
    Here we rewrite the 1d-list isAnagram example only using a dictionary instead.
    def letterCounts(s):
        counts = dict()
        for ch in s.upper():
            if ((ch >= "A") and (ch <= "Z")):
                counts[ch] = counts.get(ch, 0) + 1
        return counts
    
    def isAnagram(s1, s2):
        return (letterCounts(s1) == letterCounts(s2))
    
    def testIsAnagram():
        print("Testing isAnagram()...", end="")
        assert(isAnagram("", "") == True)
        assert(isAnagram("abCdabCd", "abcdabcd") == True)
        assert(isAnagram("abcdaBcD", "AAbbcddc") == True)
        assert(isAnagram("abcdaabcd", "aabbcddcb") == False)
        print("Passed!")
    
    testIsAnagram()