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

Question

我必须使用函数式编程来实现以下函数，其中包含从0到9的数字列表。目标是找到列表中具有最大产品的五个连续元素。该函数应该使用函数返回最大产品索引的元组和最大产品而不使用的值。

我可以很容易地实现这个没有函数式编程，但我没有任何循环实现它。 这是迄今为止我的方法，但我坚持的部分是如何循环访问数组以找到没有循环的连续五个数字。我正在尝试使用地图来做到这一点，但我不认为这是正确的。有没有可能以任何方式包含枚举？任何帮助表示赞赏。

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

Answer 1

这不会有任何显式循环或致电max功能。该函数假定输入列表中至少有五个元素，并输出一个元组(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:])创建在输入列表大小5的滑动窗口迭代器。 products = map(partial(reduce, operator.mul), win)是在win的每个元素上调用partial(reduce, operator.mul)（转换为reduce(operator.mul, ...)）的迭代器。 reduce(lambda x, y: x if x[1] > y[1] else y, enumerate(products))将计数器添加到products并返回具有最高值的索引 - 值对。

如果你需要一个更一般的版本和/或输入列表很大，你会使用itertools.islice：

from itertools import islice 

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

上面的代码使用生成器表达式这是一个循环，在技术上。这方面的一个纯功能的版本可能看起来像

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包含了所有可能的5元组的产品，然后使用reduce模仿max功能，我们发现产品中的最大值。

Answer 3

你可以做到以下几点：

• 对于每一个在range(0, len(L) - 5)
• 开始索引的索引映射到的start元组和项目的产品L[start:start + 5]
• 减少元组具有一个最高的产品
• 获取结果元组的第一个值=具有最高产品的5个元素的起始索引
• 返回切片L[result:result + 5]

该算法可以进一步改进，以避免重新计算子产品，但使用“滚动产品”，即更新为您从左至右减少，由元素除以被删除，并乘以新添加的元素。

Answer 4

这里是一个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] 

这里是做什么的：

• 在上线开始，它计算的连续产品从该列表。

• tails 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],[]] 
  

• 从这些尾巴，我们只需要那些长至少5个元素。
• 然后我们zip他们与自然数，这样我们有起始索引与它相关联。
• 从每个子集我们采取前五个元素。
• 将这五个元素传递给multiply函数。那些产品减少到一个单一的数字。
• 之后，我们回到最后一行，我们按照产品价值降序对列表进行排序。
• 从结果列表中我们只取第一个元素。
• 然后我们输出结果，即我的输入数据为(5,450)。

Answer 5

想用最大一个衬层，没有最大尝试这种

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

该解决方案使用reduce计算5-价值的产品，列表修真产生所有这些产品，元组创造了具有指标去与每一个，reduce再次得到最好的元组。

if else运算符用于在输入中没有5个值时捕捉该案例。

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) 

输出为例如呼叫：

(7, 48) 

Answer 7

势在必行范式往往是：

state = state0 
while condition: 
    # change state 

这是编程很多人的“自然”的方式，你知道如何这样做。

纯functional paradigm禁止变量，这有一些优势。它适用于通过参数（IN）和返回值（OUT）进行通信的函数。它经常使用递归函数。

的通用功能性递归方案为：

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

在这里，我们可以找到与(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]) 

无以外的功能已被定义。

您甚至可以定义没有这样做的函数，例如参见here，但可读性受损甚至更多。

执行命令

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

Python的限制通过递归深度设置为2000这种方法，并从Python 3中，由模块functools在隐藏的功能的工具。

Answer 8

使用recursion

首先，我们需要创建一个纯Python的解决方案一recursivefunction找到的product一个list：

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

，我们可以为做一些测试：

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

---

然后，我们可以用这个function在另一个recursivefunction解决你的问题：

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 

其作品！

这里有一些测试，以证明它的工作：

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