haskell 中 3 次实施的最高产品
highest product of 3 implementation in haskell
我想要在 haskell 中实现 3 问题的最高乘积的算法。这是问题陈述：
Given an array of integers, find the highest product you can get from
three of the integers.
例如给定 [1, 2, 3, 4]，算法应该 return 24。给定 [-10, -10, 5, 1, 6]，3 的最高乘积将是 600 = -10*-10*6。
我的尝试（假设第一次尝试没有底片）：
sol2' a b c [] = a*b*c
sol2' a b c (x:xs) = sol2' a' b' c' xs
where
a' = if (x > a) then x else a
b' = if (x > a && a > b) then a else b
c' = if (x > a && a > b && b > c) then b else c
sol2 li = sol2' a b c li
where a = 0
b = 0
c = 0
我用 [3, 5, 1, 2, 4, 10, 0, 4, 8, 11] 测试了实现，但是 return 值是 550，应该是 880.
正数 数
从您寻找最高数字的意义上说，您走在正确的轨道上。然而，问题是 a、b 和 c 并不总是有序的。
确实比方说我们有数字[6,2,4]。那么(a,b,c)将通过递归演化的方式是：
(0,0,0) -> (6,0,0) -> (2,6,0) -> (4,2,6)
但现在 a=4，这意味着如果我们现在遇到 3，我们将 不会 替换该值，而我们可以这样做，因为我们可以删除 2.
虽然有很多方法可以解决这个问题，但最好的方法可能是维持秩序：确保a <= b <= c.
所以我们可以使用：
sol1 = sol2' (0,0,0)
sol2' (a,b,c) [] = a*b*c
sol2' t@(a,b,c) (x:xs) = sol2' f xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
这会产生预期的结果：
Prelude> sol1 [1,2,3,4]
24
Prelude> sol1 [3, 5, 1, 2, 4, 10, 0, 4, 8, 11]
880
间奏曲：如果出现负数，请记录数字
您的程序首先将 (0,0,0) 作为前三个值。但是如果列表只包含负数（即 [-1,-2,-3]），我们当然希望首先跟踪这些。例如，我们可以通过使用列表中的元素初始化我们的元组来做到这一点：
import Data.List(sort)
sol1 (xa:xb:xc:xs) = sol2' (a,b,c) xs
where [a,b,c] = sort [xa,xb,xc]
所以现在我们取前三个元素，对它们进行排序，并将它们用作第一个元组。处理列表的其余部分。如果 sol1 没有给出至少包含三个元素的列表，此函数将出错，但在这种情况下可能没有答案。我们可以使用 Maybe 来处理函数不完全的事实。
所有个数字
当然我们也想处理负数。两个负数相乘得到一个正数。因此，通过同时跟踪两个最小的数字，我们就可以正确地进行数学计算。因此，首先我们将使用另一个参数 (d,e) 来跟踪具有 d <= e:
的最小数字
sol1_all = sol2_all' (0,0,0) (0,0)
sol2_all' (a,b,c) (d,e) [] = -- ...
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
g | x <= d = (x,d)
| x <= e = (d,x)
| otherwise = u
所以现在我们得到了最大的数字(a,b,c)和最小的数字(d,e)。如果 d 和 e 确实是负数，那么只有这样才能产生一个大的 .所以现在我们有以下几种可能来考虑a*b*c和c*d*e。所以我们可以写成：
sol2_all' (a,b,c) (d,e) [] = max (a*b*c) (c*d*e)
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
g | x <= d = (x,d)
| x <= e = (d,x)
| otherwise = u
但是请注意，这并不总是会产生正确的结果，因为我们可以计算两个元组中的两个数字。我们可以通过适当初始化元组来解决这个问题：
import Data.List(sort)
sol1_all (xa:xb:xc:xs) = sol2_all' (a,b,c) (a,b) xs
where [a,b,c] = sort [xa,xb,xc]
sol2_all' (a,b,c) (d,e) [] = max (a*b*c) (c*d*e)
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
g | x <= d = (x,d)
| x <= e = (d,x)
| otherwise = u
选择不同（可能等同）元素的基本原理
我们怎么知道我们不会使用一个元素两次？由于我们只使用 a*b*c 或 c*d*e 这将 - 在具有三个元素的列表的情况下 - 归结为 max(a*b*c,a*b*c) （a、b 和c 这里是 sort) 的结果。所以唯一性是有保证的。因为我们只会在第一个元组中添加至少大于 a 且小于 b 的元素，所以我们知道为了在两个元组中添加 x ，应该是 a <= x <= b。在那种情况下，我们将获得元组 (x,b,c) 和 (a,x)。但是由于我们在那种情况下评估 x*b*c 和 a*x*c，因此 x 不会在任何表达式中出现两次。
力扣挑战
我向 Leetcode Challenge 提交了此代码的 Python 版本并被接受：
class Solution:
def maximumProduct(self, nums):
a,b,c = d,e,_ = sorted(nums[:3])
for x in nums[3:]:
if x >= c:
a,b,c = b,c,x
elif x >= b:
a,b = b,x
elif x >= a:
a = x
if x <= d:
d,e = x,d
elif x < e:
e = x
return max(a*b*c,c*d*e)
有一些更有效的解决方案，但我倾向于更直接的解决方案，例如：
import Data.List (subsequences)
f :: (Num a, Ord a) => [a] -> a
f = maximum . map product . filter ((==3) . length) . subsequences
将函数式算法视为对集合进行转换的序列，这比将命令式循环转换为递归函数更加地道。
请注意，如果您使用非常长的列表执行此操作，而效率是一个问题，您可以先对列表进行排序，然后取最低的两个和最高的三个，算法仍然有效：
takeFirstLast xs = (take 2 sorted) ++ (drop (length sorted - 3) sorted)
where sorted = sort xs
但是，我原来的方法对于大小为 100 左右的列表来说已经足够快了，而且 lot 更容易理解。在我被告知这是实际要求之前，我不相信为了速度而牺牲可读性。
我想要在 haskell 中实现 3 问题的最高乘积的算法。这是问题陈述：
Given an array of integers, find the highest product you can get from three of the integers.
例如给定 [1, 2, 3, 4]，算法应该 return 24。给定 [-10, -10, 5, 1, 6]，3 的最高乘积将是 600 = -10*-10*6。
我的尝试（假设第一次尝试没有底片）：
sol2' a b c [] = a*b*c
sol2' a b c (x:xs) = sol2' a' b' c' xs
where
a' = if (x > a) then x else a
b' = if (x > a && a > b) then a else b
c' = if (x > a && a > b && b > c) then b else c
sol2 li = sol2' a b c li
where a = 0
b = 0
c = 0
我用 [3, 5, 1, 2, 4, 10, 0, 4, 8, 11] 测试了实现，但是 return 值是 550，应该是 880.
正数 数
从您寻找最高数字的意义上说，您走在正确的轨道上。然而，问题是 a、b 和 c 并不总是有序的。
确实比方说我们有数字[6,2,4]。那么(a,b,c)将通过递归演化的方式是：
(0,0,0) -> (6,0,0) -> (2,6,0) -> (4,2,6)
但现在 a=4，这意味着如果我们现在遇到 3，我们将 不会 替换该值，而我们可以这样做，因为我们可以删除 2.
虽然有很多方法可以解决这个问题，但最好的方法可能是维持秩序：确保a <= b <= c.
所以我们可以使用：
sol1 = sol2' (0,0,0)
sol2' (a,b,c) [] = a*b*c
sol2' t@(a,b,c) (x:xs) = sol2' f xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
这会产生预期的结果：
Prelude> sol1 [1,2,3,4]
24
Prelude> sol1 [3, 5, 1, 2, 4, 10, 0, 4, 8, 11]
880
间奏曲：如果出现负数，请记录数字
您的程序首先将 (0,0,0) 作为前三个值。但是如果列表只包含负数（即 [-1,-2,-3]），我们当然希望首先跟踪这些。例如，我们可以通过使用列表中的元素初始化我们的元组来做到这一点：
import Data.List(sort)
sol1 (xa:xb:xc:xs) = sol2' (a,b,c) xs
where [a,b,c] = sort [xa,xb,xc]
所以现在我们取前三个元素，对它们进行排序，并将它们用作第一个元组。处理列表的其余部分。如果 sol1 没有给出至少包含三个元素的列表，此函数将出错，但在这种情况下可能没有答案。我们可以使用 Maybe 来处理函数不完全的事实。
所有个数字
当然我们也想处理负数。两个负数相乘得到一个正数。因此，通过同时跟踪两个最小的数字，我们就可以正确地进行数学计算。因此，首先我们将使用另一个参数 (d,e) 来跟踪具有 d <= e:
sol1_all = sol2_all' (0,0,0) (0,0)
sol2_all' (a,b,c) (d,e) [] = -- ...
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
g | x <= d = (x,d)
| x <= e = (d,x)
| otherwise = u
所以现在我们得到了最大的数字(a,b,c)和最小的数字(d,e)。如果 d 和 e 确实是负数，那么只有这样才能产生一个大的 .所以现在我们有以下几种可能来考虑a*b*c和c*d*e。所以我们可以写成：
sol2_all' (a,b,c) (d,e) [] = max (a*b*c) (c*d*e)
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
g | x <= d = (x,d)
| x <= e = (d,x)
| otherwise = u
但是请注意，这并不总是会产生正确的结果，因为我们可以计算两个元组中的两个数字。我们可以通过适当初始化元组来解决这个问题：
import Data.List(sort)
sol1_all (xa:xb:xc:xs) = sol2_all' (a,b,c) (a,b) xs
where [a,b,c] = sort [xa,xb,xc]
sol2_all' (a,b,c) (d,e) [] = max (a*b*c) (c*d*e)
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
where f | x >= c = (b,c,x)
| x >= b = (b,x,c)
| x > a = (x,b,c)
| otherwise = t
g | x <= d = (x,d)
| x <= e = (d,x)
| otherwise = u
选择不同（可能等同）元素的基本原理
我们怎么知道我们不会使用一个元素两次？由于我们只使用 a*b*c 或 c*d*e 这将 - 在具有三个元素的列表的情况下 - 归结为 max(a*b*c,a*b*c) （a、b 和c 这里是 sort) 的结果。所以唯一性是有保证的。因为我们只会在第一个元组中添加至少大于 a 且小于 b 的元素，所以我们知道为了在两个元组中添加 x ，应该是 a <= x <= b。在那种情况下，我们将获得元组 (x,b,c) 和 (a,x)。但是由于我们在那种情况下评估 x*b*c 和 a*x*c，因此 x 不会在任何表达式中出现两次。
力扣挑战
我向 Leetcode Challenge 提交了此代码的 Python 版本并被接受：
class Solution:
def maximumProduct(self, nums):
a,b,c = d,e,_ = sorted(nums[:3])
for x in nums[3:]:
if x >= c:
a,b,c = b,c,x
elif x >= b:
a,b = b,x
elif x >= a:
a = x
if x <= d:
d,e = x,d
elif x < e:
e = x
return max(a*b*c,c*d*e)
有一些更有效的解决方案，但我倾向于更直接的解决方案，例如：
import Data.List (subsequences)
f :: (Num a, Ord a) => [a] -> a
f = maximum . map product . filter ((==3) . length) . subsequences
将函数式算法视为对集合进行转换的序列，这比将命令式循环转换为递归函数更加地道。
请注意，如果您使用非常长的列表执行此操作，而效率是一个问题，您可以先对列表进行排序，然后取最低的两个和最高的三个，算法仍然有效：
takeFirstLast xs = (take 2 sorted) ++ (drop (length sorted - 3) sorted)
where sorted = sort xs
但是，我原来的方法对于大小为 100 左右的列表来说已经足够快了，而且 lot 更容易理解。在我被告知这是实际要求之前，我不相信为了速度而牺牲可读性。