How to use functional programming to iterate and find maximum product of five consecutive numbers in a list?

Question

I have to use functional programming to implement the following function takes in a list of numbers from 0 to 9. The goal is to find the five consecutive elements of the list that have the greatest product. The function should return tuple of the index of the greatest product and the value of the greatest product without using the max function.

I can easily implement this without functional programming but I am having trouble implementing it without any loops. This is my approach so far but the part that I am stuck on is how to loop through the array to find those consecutive five numbers without loops. I am trying to use map to do that but I don't think it is correct. Is it possible to incorporate enumerate in any way? Any help is appreciated.

def find_products(L):
    val = map(lambda a: reduce(lambda x,y: x*y, L),L)
    print (val)

Answer 1

This doesn't have any explicit loops or call the max function. The function assumes that there're at least five elements in the input list and outputs a tuple (start_index, max_product).

from functools import reduce, partial
import operator

def f(l):
    win = zip(l, l[1:], l[2:], l[3:], l[4:])
    products = map(partial(reduce, operator.mul), win)
    return reduce(lambda x, y: x if x[1] > y[1] else y, enumerate(products))

In [2]: f([1, 2, 3, 4, 7, 8, 9])
Out[2]: (2, 6048)

In [3]: f([2, 6, 7, 9, 1, 4, 3, 5, 6, 1, 2, 4])
Out[3]: (1, 1512)

win = zip(l, l[1:], l[2:], l[3:], l[4:]) creates a sliding window iterator of size 5 over the input list. products = map(partial(reduce, operator.mul), win) is an iterator calling partial(reduce, operator.mul) (translates to reduce(operator.mul, ...)) on every element of win. reduce(lambda x, y: x if x[1] > y[1] else y, enumerate(products)) adds a counter to products and returns the index-value pair with the highest value.

If you need a more general version and/or the input list is large you'd use itertools.islice:

from itertools import islice

def f(l, n=5):
    win = zip(*(islice(l, i, None) for i in range(n)))
    ...

The code above uses a generator expression which is a loop, technically. A pure functional version of that might look like

from itertools import islice

def f(l, n=5):
    win = zip(*map(lambda i: islice(l, i, None), range(n)))
    ...

Answer 2

from functools import reduce #only for python3, python2 doesn't need import
def find_products(L):
    if len(L)==0:
        return 0
    if len(L) <= 5:
        return reduce( lambda x,y:x*y, L)
    pdts = ( reduce(lambda a,b:a*b,L[pos:pos+5]) for pos in range(len(L)-4)) # or pdts = map(lambda pos: reduce(lambda a,b:a*b,L[pos:pos+5],0),range(len(L)-4))
    mx = reduce(lambda x,y: x if x>y else y, pdts)
    return mx

pdts contains all the possible 5 tuple products, and then using reduce to mimic the max function, we find the maximum among the products.

Answer 3

You could do the following:

• For each start index in range(0, len(L) - 5)
• Map the index to the tuple of start and the product of items L[start:start + 5]
• Reduce the tuples to the one that has the highest product
• Get the first value of the resulting tuple = the start index of the 5 elements that have the highest product
• Return the slice L[result:result + 5]

This algorithm could be further improved to avoid re-calculating sub-products, but use a "rolling product", that is updated as you reduce from left to right, dividing by the element that was dropped, and multiplying by the new element that was added.