Enumerate partitions of a set with restrictions on the order, number, and sizes of parts.

Partition.hs

-- |Enumerate restricted partitions of a set into a sequence of sets of subsets.
partition :: [(Int, Int)]     -- ^ The i_th pair (k, n) specifies the number n of subsets in the i_th set and the size k of those subsets
          -> [a]              -- ^ The set to partition (the elements are assumed to be pairwise distinct)
          -> [([[[a]]], [a])] -- ^ The partitions, each paired with the leftover elements from the original set
partition [] xs = [([], xs)]
partition _ [] = []
partition [(0, 1)] xs = [([[[]]], xs)]
partition [(1, 1)] (x : xs) =
    ([[[x]]], xs) : [(ysss, x : zs) | (ysss, zs) <- partition [(1, 1)] xs]
partition [(k, 1)] (x : xs) =
    [([[x : ys]], zs) | ([[ys]], zs) <- partition [(k - 1, 1)] xs] ++
    [(ysss, x : zs) | (ysss, zs) <- partition [(k, 1)] xs]
partition [(k, n)] (x : xs) =
    [ ([(x : ys) : yss], zs')
    | ([[ys]], zs) <- partition [(k - 1, 1)] xs
    , ([yss], zs') <- partition [(k, n - 1)] zs
    ] ++
    [(ysss, x : zs) | (ysss, zs) <- partition [(k, n)] xs]
partition (k : ks) xs =
    [ (yss : ysss, zs')
    | ([yss], zs) <- partition [k] xs
    , (ysss, zs') <- partition ks zs
    ]