Tuesday, September 21, 2010

Algorithms in Python - Smallest free number

I have recently started reading the book "pearls of functional algorithm design" by Richard Bird. The book details various problems and functional algorithmic solutions.
I thought it would be a good exercise to solve them in Python and attempt to solve them using a functional programming language in future.
Task: find the smallest natural number not in finite set of numbers - X
The first problem illustrates the programming task in which objects are named by numbers and X represents the set of objects currently in use. The task is to find the object with the smallest name not in use. I.e. it is not in X.

Of course, there are multiple ways to solve this problem and I am not even trying to look at what may be an elegant solution.


Solution 1: which also illustrates the problem

x = [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 4, 14, 5, 17, 3, 19, 2, 6]
x.sort() # Need to sort the elements 
a  = range(0, x[-1]) # all elements in a list of which x is a subset
set_a = set(a) # use set
set_x = set(x)
Intersection_a_x = set_a & set_x
not_in_x = set_a  - Intersection_a_x
l = list(not_in_x)
print Intersection_a_x
print not_in_x
print l[0]

output: 
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 19])
set([15, 16, 18, 20, 21, 22])
15

4 comments:

  1. Obviously you can drop the `x.sort()` and change the next line into `a = range(0, max(x))`

    Another solution (doing a sort) could be:

    next(i for i, n in enumerate(sorted(x)) if i != n)

    ReplyDelete
  2. >>> min(set(x).symmetric_difference(range(max(x))))
    15

    ReplyDelete
  3. list(set(x) ^ set(range(max(x))))[0]

    ReplyDelete
  4. You can make the second set smaller than range(max(x)):

    min(set([0] + [ y+1 for y in x ]) - set(x))

    ReplyDelete