The charming adventures of an analyst and his solver.

« Thursday, November 3, 2011 »

## Know Your Time Complexities - Part 2

More on the importance of time complexity to basic programming.

In response to this post, Ben Bitdiddle inquires:

"I understand the concept of using a companion set to remove duplicates from a list while preserving the order of its elements. But what should I do if these elements are composed of smaller pieces? For instance, say I am generating combinations of numbers in which order is unimportant. How do I make a set recognize that [1,2,3] is the same as [3,2,1] in this case?"

There are a couple points that should help here:

1. While lists are unhashable and therefore cannot be put into sets, tuples are perfectly capable of this. Therefore I cannot do:

>>> s = set()
Traceback (most recent call last):
File "", line 1, in
TypeError: unhashable type: 'list'


But this works just fine (extra space added for emphasis of tuple parentheses):

>>> s.add( (1,2,3) )

2. (3,2,1) and (1,2,3) may not hash to the same thing, but tuples are easily sortable. If I sort them before adding them to a set, they look the same:

>>> tuple(sorted( (3,2,1) ))
(1, 2, 3)


If I want to be a little fancier, I can user itertools.combinations. The following generates all unique 3-digit combinations of integers from 1 to 4:

>>> from itertools import combinations
>>> list(combinations(range(1,5), 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]


Now say I want to only find those that match some condition. I can add a filter to return, say, only those 3-digit combinations of integers from 1 to 6 that multiply to a number divisible by 10:

>>> list(filter(
lambda x: not (x[0]*x[1]*x[2]) % 10,
combinations(range(1, 7), 3)
))
[(1, 2, 5), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 5),
(2, 5, 6), (3, 4, 5), (3, 5, 6), (4, 5, 6)]