The charming adventures of an analyst and his solver.
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:
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) )
(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)]