如何使用函数式编程来迭代和查找列表中五个连续数字的最大乘积?

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.

我必须使用函数式编程来实现以下功能:从0到9的数字列表。我们的目标是找到具有最伟大产品的列表中的五个连续元素。在不使用max函数的情况下，函数应该返回最伟大产品的索引和最伟大产品的值。

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)

8 个解决方案

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

这没有任何显式的循环或调用最大函数。该函数假定输入列表中至少有5个元素，并输出一个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.

win = zip(l, l[1:]， l[2:]， l[3:]， l[4:])在输入列表中创建一个5号的滑动窗口迭代器。product = map(部分(reduce, operator.mul)， win)是一个迭代器调用部分(reduce, operator.mul)(转换为reduce(操作符)。在胜利的每一个要素上。减少(x, y: x如果x[1] > y[1] y，枚举(产品))增加一个与产品的计数器，并返回具有最高价值的索引值对。

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

如果您需要一个更通用的版本和/或输入列表，那么您将使用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)))
    ...

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

pdts包含所有可能的5元组产品，然后使用reduce来模拟max函数，我们在产品中找到最大值。

#3

You could do the following:

你可以这样做:

• For each start index in range(0, len(L) - 5)
• 对于每一开始索引的范围(0,len(L) - 5)
• Map the index to the tuple of start and the product of items L[start:start + 5]
• 将索引映射到start的tuple和项目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
• 得到结果tuple的第一个值=拥有最高产品的5个元素的开始索引。
• Return the slice L[result:result + 5]
• 返回切片L[结果:结果+ 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.

该算法可以进一步改进，以避免重新计算子产品，但使用“滚动产品”，当您从左到右进行减少时，该算法会进行更新，将被删除的元素进行划分，并乘以添加的新元素。

#4

Here is a Haskell solution, which is purely functional:

这里有一个Haskell的解决方案，它是纯功能性的:

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:

  背面xs给出了所有的子集，从不同的起始值开始:

  > 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.
• 从这些反面，我们只取至少5个元素的长度。
• 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.
• 从每一个子集，我们取前5个元素。
• 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.
• 然后打印结果，也就是(5,450)输入数据。

#5

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.

这个解决方案使用reduce计算一个5值的产品，列出对生成所有这些产品的理解，tuple创建的索引与每个，再一次减少以得到最好的元组。

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

如果输入中没有5个值，则使用if else运算符来捕获该情况。

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)

#6

A Pure Python Solution using recursion

使用递归的纯Python解决方案。

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)

#7

want one liner using max and without max try this

想要一个使用max和没有max的班轮。

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

#8

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.

纯功能范式禁止变量，它具有一些优势。它与通过参数(IN)和返回值(OUT)通信的函数一起工作。它经常使用递归函数。

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:

这里我们可以找到一个(l,i,imax,prodmax)作为参数的解决方案:

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.

Python通过将递归深度设置为2000，以及从Python 3中，通过在模块功能工具中隐藏功能工具来限制这种方法。