1

我想以某种方式对列表进行分组，每个组尽可能大，并且最多包含 n 个不同的值（分组是贪婪的）。

例如：groupN 2 [2,2,3,4,5,5,4,3,4,5]应该是[[2,2,3],[4,5,5,4],[3,4],[5]]、groupN 3 [2,2,3,4,5,5,4,3,4,5]应该是[[2,2,3,4],[5,5,4,3,4,5]]和group = groupN 1。

我还没有想出一个很好的方法来实现它。你？解决方案应该尽可能通用，因为我需要更多的组条件。

4

2 回答 2

4

您可以通过定义一个辅助函数来做到这一点，该函数从列表的头部获取适当的部分。就像是

splitNDistinct :: (Eq a) => Int -> [a] -> ([a],[a])
splitNDistinct n xs = go 0 [] xs
   where 
     go _ _ [] = ([], [])
     go count seen xs'@(x:xs)
      | x `elem` seen = let (taken, rest) = go count seen xs in (x:taken, rest)
      | count /= n = let (taken, rest) = go (count+1) (x:seen) xs in (x:taken, rest)   
      | otherwise = ([], xs')

这给

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

上面的函数记录了它之前见过的元素的数量和元素，然后只在之前见过的情况下取新元素，或者如果有新元素的空间。

（上面可以通过认识到两个递归情况go具有几乎相同的结构，除了递归调用中的值count和 in的差异。但分解seen可能很容易使函数不那么干净。）

groupN可以通过反复应用来实现splitNDistinct。

想一想，可以分别在with和的递归调用中定义mapFst f (a,b) = (f a, b)和替换- 表达式，这使得它们的相似性更加烦人。letgomapFst (x:) $ go count seen xsmapFst (x:) $ go (count+1) (x:seen) xs

于 2012-11-22T23:40:25.970 回答
2

编辑：正如 dbaupp 所说，我回答了一个不同的、更简单的问题。正确的理解产生

import Data.List
import qualified Data.Set as S

groupN :: Ord a => Int -> [a] -> [[a]]
groupN n (h:t) = reverse . fmap reverse . fst $
                 foldl' add ([[h]], S.singleton h) t
  where insHead (l:t) i = (i:l):t
        add (l, s) i
          | i `S.member` s = (insHead l i, s)
          | S.size s == n  = ([i]:l, S.singleton i)
          | True           = (insHead l i, S.insert i s)

这是（我认为）正确且相当简洁，并且相对于其输入（O（n log m）对于m组唯一值和长度为n的输入列表以线性时间运行；理论最大值为O（n）使用具有恒定时间插入和查找的数据结构，我认为 dbaupp 的运行时间为 O(mn)。但是，我确实通过使用集合Eq a来加强条件，并牺牲惰性。Ord a

不正确的代码：

import Data.List

groupN :: Eq a => Int -> [a] -> [[a]]
groupN n = concatN n . group
  where concatN n l = case splitAt n l of
          (l, [])  -> return $ concat l
          (l1, l2) -> (concat l1):(concatN n l2)

您可以使用来genericSplitAt放松一下。IntIntegral

于 2012-11-23T14:14:12.790 回答