from the letters of that word. A letter can be used at most as many
times as it appears in the input word. So, "letter" can only match
words with 0, 1, or 2 t's in them.
frequencies = map (\x -> (head x, length x)) . group . sort
superset xs = \ys -> let y = frequencies ys in
length y == lx &&
and (zipWith (\(c,i) (d,j) -> c == d && i >= j) x y)
where
x = frequencies xs
lx = length x
As far as I understand the spec, this algorithm is not correct:
superset "ubuntu" "tun" == False
Is at least one 'b' necessary, yes or no? If the answer is no, the
following algorithm solves the problem and is faster then the one above:
del y = del_acc []
where del_acc _ [] = mzero
del_acc v (x:xs) | x == y = return (v++xs)
del_acc v (x:xs) = del_acc (x:v) xs
super u = not . null . foldM (flip del) u
main = interact $ unlines . filter ("ubuntu" `super`) . lines
BR,
--
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
