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