adventures in optimization

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()
    >>> s.add([1,2,3])
    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)]