Nicolas Couture-Grenier greniernic at gmail.com
Mon Mar 8 09:37:08 EST 2010

I hadn't noticed the permutation function. It's not listed in the synopis...
Nice.

Anyway, I found a better way around my little exercise.

import List
import Maybe

j :: Integral a => [a] -> Int

j xs = (fromMaybe 0 (findIndex (==False) (zipWith (<) (init xs) (tail xs))))
- 1

On Mon, Mar 8, 2010 at 9:29 AM, Daniel Fischer <daniel.is.fischer at web.de>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.
>
> >
> > A permutation is a list of n numbers (let's call it a) in {1 .. n}
> > appearing once in arbitrary order.
> >
> > The first step is to find the largest index j in the list for which a[j]
> > < a[j+1].
> >
> > The pseudocode is simple:
> >
> > j:= n-1
> >
> > while a[j] > a[j+1]
> >     j:=j-1
> >
> >
> > I've coded a haskell function to do this, but it is much uglier than the
> > pseudocode :
>
> It's not appropriate for lists, therefore, it's ugly. You can work with
> arrays and have a fairly direct correspondence:
>
> import Data.Array
>
> fun :: Array Int Int -> Int
> fun a = go (hi-1)
>   where
>      (lo,hi) = bounds a
>      go i
>        | i < lo        = i
>        | a!i > a!(i+1) = go (i-1)
>        | otherwise     = i
>
> The local "go" is our while-loop, additionally, it checks that we don't
> fall off the front of the array.
>
> When working with lists, one would typically not produce the next
> permutation from the previous, but generate the list of all permutations
> (take a look at the code of "permutations" in Data.List).
>
> >
> > j :: Integral a => [a] -> Int
> > j [] = 0
> > j xs = if (head (tail (reverse xs)) < last xs)
> >           then (length xs)-2
> >           else j (take (length xs - 1) xs)
> >
> >
> > Does anyone has a more elegant solution for this first step?
>
>
-------------- next part --------------
An HTML attachment was scrubbed...