Smallest python range from multiple lists

Question

I need to find the smallest range from a group of whole lists, using at least one element from each list.

list1=[228, 240, 254, 301, 391] list2=[212, 345, 395] list3=[15, 84, 93, 103, 216, 398, 407, 488] 

In this example, the smallest range will be [391: 398], since it covers values ​​391, 395, and 398 from three lists.

Each list will have at least one value, and there may be many more lists.

What will be the fastest computational way to find the range?

Answer 1

Since input lists are sorted, you can use merge sort, and you only need to check the range when the next value that merges comes from a list other than the last. Keep track of the last value that you saw in each of the lists, and calculate the ranges between the lowest value and the current one. This is the linear O(N) approach, where N is the total number of items in all input lists.

The following implements this approach:

 def smallest_range(*lists): iterables = [iter(it) for it in lists] iterable_map = {} for key, it in enumerate(iterables): try: iterable_map[key] = [next(it), key, it] except StopIteration: # empty list, won't be able to find a range return None lastvalues, lastkey = {}, None candidate, candidatediff = None, float('inf') while iterable_map: # get the next value in the merge sort value, key, it = min(iterable_map.values()) lastvalues[key] = value if len(lastvalues) == len(lists) and lastkey != key: minv = min(lastvalues.values()) difference = value - minv if candidatediff > difference: candidate, candidatediff = (minv, value), difference lastkey = key try: iterable_map[key][0] = next(it) except StopIteration: # this iterable is empty, remove it from consideration del iterable_map[key] return candidate 

Demo:

 >>> list1 = [228, 240, 254, 301, 391] >>> list2 = [212, 345, 395] >>> list3 = [15, 84, 93, 103, 216, 398, 407, 488] >>> smallest_range(list1, list2, list3) (391, 398) 

Answer 2

This solution slows down significantly as the lists get large / many, but do not assume that the input lists are preconfigured:

 from itertools import product def smallest_range(*arrays): result = min((sorted(numbers) for numbers in product(*arrays)), key=lambda n: abs(n[0] - n[-1])) return (result[0], result[-1]) list1 = [228, 240, 254, 301, 391] list2 = [212, 345, 395] list3 = [15, 84, 93, 103, 216, 398, 407, 488] print(smallest_range(list1, list2, list3)) 

APPLICATION:

 list1 = [228, 240, 254, 301, 391] list2 = [212, 345, 395] list3 = [15, 84, 93, 103, 216, 398, 407, 488] print(smallest_range(list1, list2, list3)) 

PRINCE:

(391, 398)