Last active
December 1, 2017 04:24
-
-
Save gdejohn/4fc88d5a08755e8d83d7310f08496e9e to your computer and use it in GitHub Desktop.
Enumerate partitions of a set with restrictions on the order, number, and sizes of parts.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- |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 | |
] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment