Given the input below, count the number of combinations of each tuple in a list, where the order of the elements doesn’t matter. For example, the combination (1,2) appears three times, as (1,2) once and (2,1) twice. And use lambdas.
|
1 2 3 |
input = [(1, 2), (2, 1), (1, 1), (1, 1), (2, 1), (2, 3, 1), (1, 2, 3)] output = {(1, 2): 3, (1, 1): 2, (1, 2, 3): 2} |
One way of solving this with a regular loop involves looping every tuple in the list and updating a dictionary:
|
1 2 3 |
y = dict() for a in input: y.update({tuple(sorted(a)): y.setdefault(tuple(sorted(a)),0)+1}) |
Dictionary keys are the sorted tuples. Then we use dict.setdefault() to set the first occurrence of each combination to 0. Afterwards, every time this tuple is seen, the value is incremented by 1.
Solution:
|
1 2 3 4 5 |
lambda x, y=dict(): [a for a in x if y.update( {tuple(sorted(a)): y.setdefault(tuple(sorted(a)),0)+1}) ] or y |
There were a few challenges with converting the loop to lambda:
- The key/pairs of dict continuously update during processing so it was critical not to return any key/pairs until all the processing was complete. Placing the dict at the beginning of the list comprehension would produce a list consisting of temporary key/value pairs. Also, the return of dict.update() is always None, so placing it at the beginning of the list comprehension would result in a list like [None, None, None, None...] .
- How to return this dict without creating it as a parameter outside the lambda?
The solution involved some algebraic trickery. Note that the list comprehension contains an if statement that will add to the list only if something is true. Since
dict.update() always returns None – the final result is always an empty list. How does that help us?
The last part of the lambda compares this list to the dictionary. An empty list always evaluates to false and the dict evaluates to true since it contains elements. Therefore, the returned value of this lambda is effectively the dictionary.
Update 8/13/2015
A while later after posting this I found an even simpler solution using
collections.Counter which is implemented as a dictionary that holds elements as keys and their counts as values; essentially what was done above:
|
1 2 3 4 5 6 7 |
input = [(1, 2), (2, 1), (1, 1), (1, 1), (2, 1), (2, 3, 1), (1, 2, 3)] c = collections.Counter() for seq in input: c[tuple(sorted(seq))] += 1 >>> c Counter({(1, 2): 3, (1, 1): 2, (1, 2, 3): 2}) |