CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Sets and Dictionaries: 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()