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

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 2

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

Answer 4

Here is a Haskell solution, which is purely functional:

import Data.List

multiply :: [Int] -> Int
multiply = foldr (*) 1

consecutiveProducts :: [Int] -> [(Int,Int)]
consecutiveProducts xs =
    [(i,multiply $ take 5 h) | (i,h) <- zipped, length h >= 5]
    where
        indices = reverse [0..(length xs)]
        zipped = zip indices (tails xs)

myComp (i1,h1) (i2,h2) = compare h2 h1

main = print $ head $ sortBy myComp $ consecutiveProducts [4,5,3,1,5,3,2,3,5]

Here is what it does:

• Starting in the last line, it computes the consecutive products from that list.

• tails xs gives all the subsets starting with different starting values:

  > tails [4,5,3,1,5,3,2,3,5]
  [[4,5,3,1,5,3,2,3,5],[5,3,1,5,3,2,3,5],[3,1,5,3,2,3,5],[1,5,3,2,3,5],[5,3,2,3,5],[3,2,3,5],[2,3,5],[3,5],[5],[]]
  

• From these tails we only take those that are at least 5 elements long.
• Then we zip them with natural numbers such that we have the starting index associated with it.
• From each of the subsets we take the first five elements.
• These five elements are passed to the multiply function. There those are reduced to a single number, the product.
• After that we go back to the last line, we sort the list by the product value descending.
• From the resulting list we only take the first element.
• And then we print the result, which is (5,450) for my input data.

Answer 5

want one liner using max and without max try this

from numpy import prod
l=[2,6,7,9,1,4,3]
max([prod(l[i:i+5]) for i in range(len(l))])
sorted([prod(l[i:i+5]) for i in range(len(l))])[-1]  // without max

Answer 6

This solution uses reduce to calculate a 5-value product, list comprehension for generating all of those products, tuple creation for having the index to go with each, reduce again to get the best tuple.

An if else operator is used to catch the case when there are no 5 values in the input.

from functools import reduce

def find_products(values):
    return None if len(values) < 5 else reduce(
        lambda best, this: this if this[1] > best[1] else best,
        [(i, reduce(lambda a,b: a*b, values[i:i+5], 1)) for i in range(0, len(values)-4)]
    )

result = find_products([1, 0, 8, 3, 5, 1, 0, 2, 2, 3, 2, 2, 1])
print (result)

Output for the example call is:

(7, 48)

Answer 7

Imperative paradigm is often:

 state = state0
 while condition:
   # change state 

This is the "natural" way of programming for lot of people and you know how do that in this way.

The pure functional paradigm forbid variables, which have some advantages . It works with functions which communicates through parameters(IN) and return values(OUT). It frequently uses recursive functions.

A generic functional recursive scheme is :

f = lambda *args : result(*args) if  condition(*args) else f(*newparams(*args))   

Here we can find a solution with (l,i,imax,prodmax) as parameters, and:

condition = lambda  l,i,_,__ : i>=len(l)-5        

result = lambda _,__,*args : args

newparams = lambda l,i,imax,prodmax: (l, i+1, imax, prodmax)  \
            if   l[i]*l[i+1]*l[i+2]*l[i+3]*l[i+4] <= prodmax  \
            else (l, i+1, i, l[i]*l[i+1]*l[i+2]*l[i+3]*l[i+4]) 

None other than functions have been defined.

You can even define no functions to do that, see here for example, but readability suffers even more.

Run :

In [1]: f([random.randint(0,9) for i in range (997)],0,0,0)
Out[1]: (386, 59049)                

Python limits this approach by setting recursive depth to 2000, and from Python 3, by hiding functional tools in the module functools.

Answer 8

A Pure Python Solution using recursion

First, we need to create a recursive function to find the product of a list:

def product(l, i=0, s=1):
    s *= l[i]
    if i+1 < len(l):
        return product(l, i+1, s)
    return s

which we can do some tests for:

>>> product([1, 2, 3])
6
>>> product([1, 1, 1])
3
>>> product([2, 2, 2])
8

---

Then, we can use this function in another recursive function to solve your problem:

def find_products(l, i=0, t=(0, -1)):
     p = product(l[i:i+5])
     if p > t[1]:
         t = (i, p)
     if i+5 < len(l):
         return find_products(l, i+1, t)
     return t

which works!

Here are some tests to show it working:

>>> find_products([1, 1, 5, 5, 5, 5, 5, 1, 1])
(2, 3125)
>>> find_products([1, 1, 1, 1, 1, 0, 0, 0, 0])
(0, 1)
>>> find_products([1, 4, 5, 2, 7, 9, 3, 1, 1])
(1, 2520)