Haskell Quiz/Splitting the Loot/Solution TomPlick
Using the examples from http://www.rubyquiz.com/quiz65.html:
> splitLoot 3 [1..4]  > splitLoot 2 [9, 12, 14, 17, 23, 32, 34, 40, 42, 49] [[[9,12,32,34,49],[14,17,23,40,42]],[[14,17,23,40,42],[9,12,32,34,49]]] > head $ splitLoot 3 [1..4] *** Exception: Prelude.head: empty list > head $ splitLoot 2 [9, 12, 14, 17, 23, 32, 34, 40, 42, 49] [[9,12,32,34,49],[14,17,23,40,42]]
import Control.Monad.List partitionSet :: [a] -> [([a], [a])] partitionSet  = [(, )] partitionSet (x:xs) = concat [[(x:p1, p2), (p1, x:p2)] | (p1, p2) <- partitionSet xs] type Distribution = [[Integer]] splitLoot :: Integer -> [Integer] -> [Distribution] splitLoot 0  = return  splitLoot 0 _ = mzero splitLoot numPeople jewels = let (share, leftovers) = (sum jewels) `quotRem` numPeople in if leftovers /= 0 then  else do (mine, restOfJewels) <- partitionSet jewels if (sum mine) == share then do restOfDivision <- splitLoot (numPeople - 1) restOfJewels return (mine : restOfDivision) else mzero
partitionSet takes a list and returns a list of ways to divide the set into two. For example,
partitionSet [1, 2] returns
splitLoot operates by trying to take one person's loot from the jewels, then dispersing the remainder to the rest of the people. First, care must be taken that an equal distribution is possible (hence
leftovers /= 0). Then, we examine each partition of the jewels into two sets
restOfJewels. For each
mine that adds up to a fair share, we attempt division of
restOfJewels among the rest of the people.
splitLoot uses the list monad; under the list monad, a binding of the form
x <- y means roughly that
x is to take on each member of the list
y, one at a time.
splitLoot returns all solutions; if only one is desired, call
head on the result.