[Haskell-beginners] Re: Translating a while
Heinrich Apfelmus
apfelmus at quantentunnel.de
Mon Mar 8 11:07:23 EST 2010
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
More information about the Beginners
mailing list