如何在Haskell中生成偶数长度列表的所有全覆盖两两配对方案

实现代码 #

无需额外筛选，直接通过递归构造即可得到目标结果，代码如下：

allPairings :: [a] -> [[(a, a)]]
-- 边界：空列表唯一的合法配对方案是空方案
allPairings [] = [[]]
allPairings (first:rest) = do
    -- 依次取剩余列表中的每个元素和首元素配对，同时得到去掉该元素后的剩余列表
    (paired, left) <- pickEach rest
    -- 递归生成剩余列表的所有合法配对方案
    subPairings <- allPairings left
    -- 拼接当前配对和子方案，得到完整配对
    return $ (first, paired) : subPairings
  where
    -- 辅助函数：返回列表中每个元素，以及去掉该元素后的剩余列表
    pickEach :: [a] -> [(a, [a])]
    pickEach [] = []
    pickEach (x:xs) = (x, xs) : map (\(v, vs) -> (v, x:vs)) (pickEach xs)

思路说明 #

• 你之前实现的pairs函数仅生成了列表中所有独立的二元组合，每个输出项是单个二元组，而非覆盖全部元素的完整配对方案，因此无法通过简单筛选得到目标结果。
• 上述实现采用递归构造逻辑：
  1. 固定列表第一个元素，依次和剩余每个元素配对
  2. 对去掉这两个元素的剩余列表递归生成所有合法配对
  3. 拼接当前配对和递归得到的子方案，即可得到所有覆盖全部元素的不重复配对方案

测试示例 #

输入allPairings [1,2,3,4]，输出结果为：

[[(1,2),(3,4)],[(1,3),(2,4)],[(1,4),(2,3)]]

和需求示例完全匹配，若列表长度为2n，最终会生成(2n-1)!!种不同的配对方案，符合组合数学计算结果。

内容的提问来源于stack exchange，提问作者user17480759