Determining the minimum of a list of n elements

Question

I am having trouble developing an algorithm to determine the minimum of a list of n items. This is not the case of finding the minimum of an array of length n, which is simple:

min = A[0] for i in range(1, len(A)): if min > A[i]: min = A[i] print min 

But my list contains objects:

 class Object: def __init__(self, somelist): self.classification = somelist[0] # String self.type = somelist[1] # String self.first = somelist[2] # Integer self.last = somelist[3] # Integer 

And for the same 'classification | type 'I have m elements and I want to find the minimum element of the same' classification | type ', comparing the difference between the first and last.

Example:

 obj1 = Object(['A', 'x', 4, 17]) obj2 = Object(['A', 'y', 5, 20]) obj3 = Object(['B', 'z', 10, 27]) obj4 = Object(['B', 'z', 2, 15]) obj5 = Object(['B', 'z', 20, 40]) obj6 = Object(['A', 'x', 6, 10]) obj7 = Object(['A', 'x', 2, 9]) list = [obj1, obj2, obj3, obj4, obj5, obj6, obj7] 

So, I need an algorithm to determine list minima:

A | x → Object (['A', 'x', 6, 10])

B | z → Object (['B', 'z', 2, 15])

A | y → Object (['A', 'y', 5, 20])

Thanks!

Answer 1

 import itertools group_func = lambda o: (o.classification, o.type) map(lambda pair: (pair[0], min(pair[1], key=lambda o: o.last - o.first)), itertools.groupby(sorted(l, key=group_func), group_func)) 

group_func returns a tuple key containing the classification of the object, then enter (for example, ('A', 'x') ). This is first used to sort the list l ( sorted call). Then we call groupby in the sorted list, using group_func to group in the sublists. Every time a key changes, we have a new sublist. Unlike SQL, groupby requires that the list be pre-sorted on the same key. map displays the result of the groupby function. For each group, map returns a tuple. The first element is pair[0] , which is the key ('A', 'x') . The second is the minimum of the group ( pair[1] ), defined by the key last - first .

Answer 2

 filtered = [obj for obj in lst if obj.classification == 'A' and obj.type = 'x'] min(filtered, key=lambda x: x.last - x.first) 

Note: do not name the variable list : it is a shadow inline.

Answer 3

Here is a simple, understandable, dynamic procedural way around this:

 class Object: def __init__(self, somelist): self.classification = somelist[0] # String self.type = somelist[1] # String self.first = somelist[2] # Integer self.last = somelist[3] # Integer def weight(self): return self.last - self.first def __str__(self): return "Object(%r, %r, %r, %r)" % (self.classification, self.type, self.first, self.last) __repr__ = __str__ obj1 = Object(['A', 'x', 4, 17]) obj2 = Object(['A', 'y', 5, 20]) obj3 = Object(['B', 'z', 10, 27]) obj4 = Object(['B', 'z', 2, 15]) obj5 = Object(['B', 'z', 20, 40]) obj6 = Object(['A', 'x', 6, 10]) obj7 = Object(['A', 'x', 2, 9]) olist = [obj1, obj2, obj3, obj4, obj5, obj6, obj7] mindict = {} for o in olist: key = (o.classification, o.type) if key in mindict: if o.weight() >= mindict[key].weight(): continue mindict[key] = o from pprint import pprint pprint(mindict) 

and here is the conclusion:

 {('A', 'x'): Object('A', 'x', 6, 10), ('A', 'y'): Object('A', 'y', 5, 20), ('B', 'z'): Object('B', 'z', 2, 15)} 

Note: __str__ , __repr__ and pprint are only for getting a fancy printout, this is not necessary. Also the above code works unchanged in Python 2.2 to 2.7.

Runtime : O (N), where N is the number of objects in the list. Object sorting solutions are O (N * log (N)) on average. Another solution is O (K * N), where K <= N is the number of unique (classification, type) keys obtained from objects.

Used additional memory : only O (K). Other solutions are O (N).