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の違いを除いて、 の 2 つの再帰的なケースがほとんど同じ構造を持っていることを認識することで、上記はおそらくきれいになる可能性があります。countseen

groupNを繰り返し適用することで実装できますsplitNDistinct。

考えてみると、 withとeach の再帰呼び出しで -expressions を定義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)

これは (私が思うに) 正しく、かなり簡潔であり、その入力に対して線形時間で実行されます (m の一意の値のグループと長さ n の入力リストの O(n log m); 理論上の最大値は 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してリラックスするIntことができますIntegral。

于 2012-11-23T14:14:12.790 に答える