Returning the second smallest number in a nested list using recursion

Question

I need to return the second smallest number in a python list with recursion and without loops . What I did was created by a helper function that returns a tuple of (smallest, second smallest) values ​​in a list, and then I just take tuple[1] in my second_smallest func.

 def s_smallest(L): if(len(L) == 2): if (L[0] >= L[1]): return (L[1],L[0]) else: return (L[0],L[1]) else: first_smallest,second_smallest = s_smallest(L[1:]) if L[0] >= first_smallest and L[0] <= second_smallest: return (first_smallest, L[0]) elif L[0] <= first_smallest: return (L[0], first_smallest) else: return (first_smallest, second_smallest) 

This works, but now I need to handle nested lists , so s_smallest([1,2,[3,0]]) should return (0,1) . I tried to do this:

 if isinstance(L[0],list): first_smallest,second_smallest = s_smallest(L[0]) else: first_smallest,second_smallest = s_smallest(L[1:]) 

to get the first smallest and second smallest values ​​if it is a list, but I get the error builtins.TypeError: unorderable types: int() >= list() . How can I fix this problem for working with nested lists?

Answer 1

I could suggest separating the unsesting list and reducing min to two separate, well-defined tasks

• deepReduce will reduce the list of lists using the specified reduction function
• deepMin performs deepReduce with min

 import math # used for math.inf def min (x,y): return x if x < y else y def deepReduce (f, y, xs): if not xs: return y elif isinstance(xs[0], list): return deepReduce(f, deepReduce(f, y, xs[0]), xs[1:]) else: return deepReduce(f, f(y, xs[0]), xs[1:]) def deepMin (xs): return deepReduce (min, math.inf, xs) data = [1,2,[7,[6,1,3,[0,4,3]],3,4],2,1] print(deepMin(data)) # 0 

Oh, but you said you want the second smallest number. Recycle this code a bit. Of course, I knew this all the time, but the answer to this question twice allows me to demonstrate the universality of this particular implementation - Changes in bold

 def min2 (xs, y): # x1 is the smallest, x2 is second smallest x1, x2 = xs if (y < x1) and (y < x2): return (y, x2) elif y < x2: return (x1, y) else: return (x1, x2) def deepMin 2 (xs): # notice we change to use tuple of math.inf now x1, x2 = deepReduce ( min2 , (math.inf, math.inf ) , xs) return x2 data = [1,2,[7,[6,1,3,[0,4,3]],3,4],2,1] print(deepMin 2 (data)) # 1 

I should point out that we don’t need to touch deepReduce , which is the point - we should be able to do any arbitrary deep operation in our nested list without the need to statically code this behavior in our function.

Now you can write any deep reducer you want and name it with deepReduce

Answer 2

Complete solution

Using nothing but functools.reduce , there are no loops to process arbitrary attachment lists:

 import functools def helper(acc, x): if type(x) is list: return functools.reduce(lambda acc, x: helper(acc, x), x, acc) else: if x < acc[0]: return (x, acc[0]) elif x < acc[1]: return (acc[0], x) else: return (acc[0], acc[1]) def second_smallest(l): if len(l) < 2: return None else: if l[0] <= l[1]: return functools.reduce(lambda acc, x: helper(acc, x), l[2:], (l[0], l[1])) else: return functools.reduce(lambda acc, x: helper(acc, x), l[2:], (l[1], l[0])) >>> second_smallest([1,2,[0,3,[-1,-2]]]) (-2, -1)