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 - XThe 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

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

ReplyDeleteAnother solution (doing a sort) could be:

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

>>> min(set(x).symmetric_difference(range(max(x))))

ReplyDelete15

list(set(x) ^ set(range(max(x))))[0]

ReplyDeleteYou can make the second set smaller than range(max(x)):

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