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()

   Select Visualize Run


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()

   Select Visualize Run


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()

   Select Visualize Run


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()

   Select Visualize Run