gistfile1.hs

--- Generates the list of summands permutations for given 'sum'.
--- Every permutation is the list of numbers, with length of 'summandsNum';
--- the sum of all items in a permutation equals to 'sum'. Function doesn't
--- generate duplicate permutations, which differ only in order.
summandsPermutations :: Integral a => a -> a -> [[a]]
summandsPermutations summandsNum sum
    | summandsNum >= 1 && summandsNum <= sum =
    f summandsNum 1 sum
    where f n m s
            | n==1 && m<=s = [[s]]
            | n>0  && m<=s = concat
                $ takeWhile (not.null)
                $ map (\(i,rs) -> map (i:) rs)
                $ map (\i -> (i, f (n-1) i (s-i)))
                $ [m..]
            | otherwise    = []

--- Generates all possible choises of 'k' items from the list.
--- Every choise is a tuple of two lists: the list of choosen items and
--- the list of rest items.
choisesWithRests :: Int -> [a] -> [([a],[a])]
choisesWithRests 0 xs = [([],xs)]
choisesWithRests k [] = []
choisesWithRests k (x:xs) =
    map (\(sx,sr) -> (x:sx,sr)) (choisesWithRests (k-1) xs) ++
    map (\(sx,sr) -> (sx,x:sr)) (choisesWithRests k xs)

--- Generates all possible variants of keyboard with 'keysNum' of keys
--- labeled each with one or more letter from 'letters'.
--- TODO: get rid of fromIntegral. 
keyboardVariants :: Integral a => a -> [b] -> [[[b]]]
keyboardVariants keysNum letters = id
    $ concatMap (g letters)
    $ summandsPermutations (fromIntegral keysNum) (length letters)
    where g _ [] = [[]]
          g ls (p:ps) = id
              $ map (\(cs,rs) -> concatMap (cs:) $ g rs ps)
              $ choisesWithRests p ls