13

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)
7
  • 3
    map and reduce use loops behind the scenes, trying to avoid using loops in list-comprehensions for example is going to be pretty difficult and has no real benefit.
    – Joe Iddon
    Nov 18, 2017 at 13:28
  • 4
    You can almost straightforwardly avoid loops if instead you use recursion. Haskell does it this way. However, Haskell has optimizations for this, Python likely does not. So you will quickly run into the maximum recursion depth. — What is your motivation to do it in a functional style, anyway? Nov 18, 2017 at 13:54
  • 10
    functional programming =/= avoiding loops.
    – trincot
    Nov 18, 2017 at 15:37
  • I realize that you said max is not allowed, but it's worth noting that, in real functional programming, the best way to do this would probably be to use the max function with a sliding window iterator (e.g. max(sliding(L, 5), key=product) for suitable definitions of sliding and product). Nov 18, 2017 at 23:31
  • IMO, loop vs recursion is just an instance of sequential thinking vs divide-and-conquer.
    – Alex Vong
    Nov 19, 2017 at 0:44

8 Answers 8

7

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)))
    ...
4
  • This looks good and probably the closest to what OP is expecting. Nov 18, 2017 at 15:59
  • BTW, you could use win = zip(*(l[i:] for i in range(5))) for a more general answer. Nov 18, 2017 at 16:11
  • I am still confused as to what the partial operation is doing? what would happen if we didn't use it?
    – aa1
    Nov 19, 2017 at 3:13
  • @vaultah Thank you so much for your help! I think your answer expressed the code in a really functional programming way!
    – aa1
    Nov 19, 2017 at 16:54
7
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.

2
  • 1
    Please correct me if I'm wrong, but we cannot use conditional statements in functional programming right? Or any loops inside the list comprehension?
    – aa1
    Nov 18, 2017 at 14:41
  • 5
    @comp.eng. there's nothing wrong with conditionals in functional programming. Haskell has if, guard clauses and pattern matching, all forms of conditionals -- there's no way to stop recursion without conditions.
    – Mephy
    Nov 18, 2017 at 14:54
2

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.

0

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

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)
0

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)
2
  • You requested some feedback. This code looks sensible. You will eventually have a problem with the maximum recursion depth in Python. Also the overhead of calling a function in Python is not negligible because they are all virtual. So I would think that using reduce and map would be faster and easier to read. I still don't understand the motivation of the OP. Nov 19, 2017 at 20:01
  • @MartinUeding Yea, I hadn't considered the maximum recursion depth good point. And I agree that what the OP wants isn't really practical
    – Joe Iddon
    Nov 19, 2017 at 20:03
0

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
1
  • max prohibited :) .
    – B. M.
    Nov 19, 2017 at 16:11
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.