Daniel Fischer wrote:
Am Montag 08 März 2010 14:49:15 schrieb Nicolas Couture-Grenier:
I'm learning Haskell and I'm trying to translate a pseudocode algorithm to generate the next permutation from a previous permutation.
Don't try to translate it directly. In Haskell, generally a different approach than for imperative (pseudo-) code is better.
For instance, like this: -- next permutation in lexicographic order next :: Ord a => [a] -> Maybe [a] next [x] = Nothing next (x:xs) = case next xs of Nothing -> case span (> x) xs of ([],xs) -> Nothing (ys,zs) -> Just (last ys : reverse (init ys ++ x : zs)) Just xs' -> Just (x:xs') Since there is exactly one permutation that doesn't have a next one, the result has to be wrapped in a Maybe type. Of course, this is very handy and natural for the recursive formulation of the algorithm anyway. Since the above definition contains some thought™, here a helper function to test its correctness: permutationsFrom xs = xs : unfoldr (fmap (\x -> (x,x)) . next) xs correct n = let perms = permutationsFrom [1..n] in length perms == product [1..n] && sort perms == perms In other words, repeatedly applying next to the trivial permutation [1..n] should eventually yield a sorted list of all permutations. *Main> correct 8 True Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com