list - 公平地划分列表

Question

我确信这是一个相当常见的事情，但我找不到任何东西(我的互联网搜索能力不强)。

我有一个函数，可以将一个列表分组为每个包含 N 个元素的列表，如果列表的长度不能被 N 整除，则最终的子列表小于 N。一些示例:

groupEvery 2 [1,2,3,4]              = [[1,2],[3,4]]
groupEvery 4 [1,2,3,4,5,6,7,8,9,10] = [[1,2,3,4], [5,6,7,8], [9,10]]

我想要的是获取一个列表和一个正整数n(在上面的例子中n可以说是2和3)并将其划分为n 个列表的新列表。它应该适用于任何类型的列表，并生成大小差异尽可能小的子列表。

所以我想要:

fairPartition 3 [1,2,3,4,5,6,7,8,9,10] = [[1,2,3,4], [5,6,7], [8,9,10]]

或者子列表的任意组合，只要有两个长度为 3 的子列表和一个长度为 4 的子列表即可。

使用 groupEvery 的天真尝试:

fairPartition :: Int -> [a] -> [[a]]
fairPartition n xs = groupEvery ((length xs `div` n) + 1) xs

fairPartition 4 [1..10] = [[1,2,3],[4,5,6],[7,8,9],[10]]

但是正如您所看到的，(3,3,3,1) 不是一个公平的长度分布，对于较小长度的列表，它甚至不会返回正确数量的子列表:

# Haskell, at GHCi
*Main> let size = 4 in map (\l -> length . fairPartition 4 $ [1..l]) [size..25]
[2,3,3,4,3,3,4,4,3,4,4,4,4,4,4,4,4,4,4,4,4,4]

我想要一个可以轻松翻译成 Haskell 的 {pseudo,actual} 代码函数或解释(恒等翻译是最好的!)。

谢谢。

Answer 1

您可以使用split包的splitPlaces函数用于此。

import Data.List.Split

fairPartition n xs = case length xs `quotRem` n of
    (q, r) -> splitPlaces (replicate r (q+1) ++ replicate (n-r) q) xs