基于numberOfOccurrences与isPermutation实现两类5元素序列校验函数

需求说明 #

给定一个从列表[1..6]中抽取的5个元素组成的升序列表，需要实现两个函数：

• 校验序列中是否恰好存在4个相等元素（例如[1,1,1,1,2]、[4,4,4,4,5]、[1,5,5,5,5]）；
• 校验序列中是否恰好存在3个相等元素且恰好存在2个相等元素（例如[2,2,2,4,4]、[1,1,1,2,2]）。

可用工具函数 #

可使用numberOfOccurrences、isPermutation、isSorted、maximum、minimum等函数，其中numberOfOccurrences与isPermutation的实现如下：

numberOfOccurrences :: Eq a => a -> [a] -> Int
numberOfOccurrences _ [] = 0
numberOfOccurrences x (y:ys)
  | x == y    = 1 + numberOfOccurrences x ys
  | otherwise = numberOfOccurrences x ys

isPermutation :: Eq a => [a] -> [a] -> Bool
isPermutation [] [] = True
isPermutation xs [] = False
isPermutation xs (y:ys) | length xs /= length (y:ys) = False
                        | otherwise = isPermutation (delete y xs) ys

之前的错误解法 #

我针对第二个函数最初写了这段代码：

p :: [Int] -> Bool
p xs = 3 == maximum (map length (group xs))

经Daniel Wagner指出错误后，修改为：

p :: [Int] -> Bool
p xs = 3 == maximum ns && length ns == 2
    where 
        ns = (map length (group xs))

但该解法不符合要求，必须使用numberOfOccurrences和isPermutation来实现，求相关解法提示。

解法提示 #

第一个函数（恰好4个相等元素） #

因为输入是升序列表，符合条件的序列只有两种形态：要么前4个元素相同，要么后4个元素相同。用numberOfOccurrences可以快速判断：

• 统计列表最小值的出现次数，如果等于4，就符合条件；
• 否则统计列表最大值的出现次数，如果等于4，也符合条件；
• 其他情况都不符合。

第二个函数（恰好3个+2个相等元素） #

这种序列的核心是：只有两种不同元素，且一个出现3次，另一个出现2次。可以从两个方向实现：

1. 基于次数统计：
   • 取列表中的第一个元素x，用numberOfOccurrences统计它的出现次数cnt；
   • 如果cnt是3，那么剩下的元素必须全是同一个值（即该值的numberOfOccurrences结果为2）；
   • 如果cnt是2，那么剩下的元素必须全是同一个值且出现次数为3；
   • 其他情况直接排除。
2. 基于排列匹配：
   • 生成所有合法的3+2模式（比如[k,k,k,m,m]或[k,k,m,m,m]，其中k和m是1-6中不同的整数）；
   • 因为输入是升序的，直接判断输入列表是否和某个升序的合法模式相等，或者用isPermutation判断输入是否是这些模式的排列。

内容的提问来源于stack exchange，提问作者F. Zer