1 from operator import itemgetter
2 from heapq import nlargest
3 from itertools import repeat, ifilter
7 """Dict subclass for counting hashable objects. Sometimes called a bag
8 or multiset. Elements are stored as dictionary keys and their counts
9 are stored as dictionary values.
12 Counter({'y': 3, 'z': 2, 'g': 1})
16 def __init__(self, iterable=None, **kwds):
17 """Create a new, empty Counter object. And if given, count elements
18 from an input iterable. Or, initialize the count from another mapping
19 of elements to their counts.
21 >>> c = Counter() # a new, empty counter
22 >>> c = Counter('gallahad') # a new counter from an iterable
23 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping
24 >>> c = Counter(a=4, b=2) # a new counter from keyword args
27 self.update(iterable, **kwds)
29 def __missing__(self, key):
32 def most_common(self, n=None):
33 """List the n most common elements and their counts from the most
34 common to the least. If n is None, then list all element counts.
36 >>> Counter('abracadabra').most_common(3)
37 [('a', 5), ('r', 2), ('b', 2)]
41 return sorted(self.iteritems(), key=itemgetter(1), reverse=True)
42 return nlargest(n, self.iteritems(), key=itemgetter(1))
45 """Iterator over elements repeating each as many times as its count.
47 >>> c = Counter('ABCABC')
48 >>> sorted(c.elements())
49 ['A', 'A', 'B', 'B', 'C', 'C']
51 If an element's count has been set to zero or is a negative number,
52 elements() will ignore it.
55 for elem, count in self.iteritems():
56 for _ in repeat(None, count):
59 # Override dict methods where the meaning changes for Counter objects.
62 def fromkeys(cls, iterable, v=None):
63 raise NotImplementedError(
64 "Counter.fromkeys() is undefined. Use Counter(iterable) instead."
67 def update(self, iterable=None, **kwds):
68 """Like dict.update() but add counts instead of replacing them.
70 Source can be an iterable, a dictionary, or another Counter instance.
72 >>> c = Counter('which')
73 >>> c.update('witch') # add elements from another iterable
74 >>> d = Counter('watch')
75 >>> c.update(d) # add elements from another counter
76 >>> c['h'] # four 'h' in which, witch, and watch
80 if iterable is not None:
81 if hasattr(iterable, "iteritems"):
84 for elem, count in iterable.iteritems():
85 self[elem] = self_get(elem, 0) + count
87 dict.update(self, iterable) # fast path when counter is empty
91 self[elem] = self_get(elem, 0) + 1
96 "Like dict.copy() but returns a Counter instance instead of a dict."
99 def __delitem__(self, elem):
100 "Like dict.__delitem__() but does not raise KeyError for missing values."
102 dict.__delitem__(self, elem)
106 return "%s()" % self.__class__.__name__
107 items = ", ".join(map("%r: %r".__mod__, self.most_common()))
108 return "%s({%s})" % (self.__class__.__name__, items)
110 # Multiset-style mathematical operations discussed in:
111 # Knuth TAOCP Volume II section 4.6.3 exercise 19
112 # and at http://en.wikipedia.org/wiki/Multiset
114 # Outputs guaranteed to only include positive counts.
116 # To strip negative and zero counts, add-in an empty counter:
119 def __add__(self, other):
120 """Add counts from two counters.
122 >>> Counter('abbb') + Counter('bcc')
123 Counter({'b': 4, 'c': 2, 'a': 1})
127 if not isinstance(other, Counter):
128 return NotImplemented
130 for elem in set(self) | set(other):
131 newcount = self[elem] + other[elem]
133 result[elem] = newcount
136 def __sub__(self, other):
137 """Subtract count, but keep only results with positive counts.
139 >>> Counter('abbbc') - Counter('bccd')
140 Counter({'b': 2, 'a': 1})
143 if not isinstance(other, Counter):
144 return NotImplemented
146 for elem in set(self) | set(other):
147 newcount = self[elem] - other[elem]
149 result[elem] = newcount
152 def __or__(self, other):
153 """Union is the maximum of value in either of the input counters.
155 >>> Counter('abbb') | Counter('bcc')
156 Counter({'b': 3, 'c': 2, 'a': 1})
159 if not isinstance(other, Counter):
160 return NotImplemented
163 for elem in set(self) | set(other):
164 newcount = _max(self[elem], other[elem])
166 result[elem] = newcount
169 def __and__(self, other):
170 """Intersection is the minimum of corresponding counts.
172 >>> Counter('abbb') & Counter('bcc')
176 if not isinstance(other, Counter):
177 return NotImplemented
180 if len(self) < len(other):
181 self, other = other, self
182 for elem in ifilter(self.__contains__, other):
183 newcount = _min(self[elem], other[elem])
185 result[elem] = newcount
189 if __name__ == "__main__":
192 print(doctest.testmod())