我必须使用函数式编程来实现以下函数,从0到9获取数字列表。目标是找到列表中具有最佳产品的五个连续元素。该函数应返回最大乘积的索引元组和最大乘积的值,而不使用 max 函数。
我可以在没有函数式编程的情况下轻松实现它,但我在没有任何循环的情况下实现它时遇到了麻烦。到目前为止,这是我的方法,但我坚持的部分是如何遍历数组以找到没有循环的连续五个数字。我正在尝试使用地图来做到这一点,但我认为这是不正确的。是否可以以任何方式合并枚举?任何帮助,不胜感激。
def find_products(L):
val = map(lambda a: reduce(lambda x,y: x*y, L),L)
print (val)
这没有任何显式循环或调用 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)))
...
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
函数,我们在产品中找到最大值。
您可以执行以下操作:
- 对于
range(0, len(L) - 5)
中的每个起始索引 - 将索引映射到
start
元组和项的乘积L[start:start + 5]
将元组 - 减少到具有最高乘积的元组
- 获取生成的元组的第一个值 = 具有最高乘积的 5 个元素的起始索引
- 返回切片
L[result:result + 5]
此算法可以进一步改进以避免重新计算子产品,但使用"滚动乘积",当您从左到右减少时,它会更新,除以删除的元素,然后乘以添加的新元素。
这是一个 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)
。
此解决方案使用 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)
使用recursion
的纯Python解决方案
首先,我们需要创建一个recursive
function
来查找list
的product
:
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
然后,我们可以在另一个recursive
function
中使用此function
来解决您的问题:
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)
想要一个使用 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
命令式范式通常是:
state = state0
while condition:
# change state
对于很多人来说,这是"自然"的编程方式,你知道如何以这种方式做到这一点。
纯函数范式禁止变量,这有一些优点。它与通过参数(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])
只定义了函数。
您甚至可以不定义任何函数来执行此操作,例如请参阅此处,但可读性受到的影响更大。
跑:
In [1]: f([random.randint(0,9) for i in range (997)],0,0,0)
Out[1]: (386, 59049)
Python 通过将递归深度设置为 2000 来限制这种方法,从 Python 3 开始,通过在模块functools
中隐藏功能工具来限制这种方法。