next_permutation being a subroutine in the C++ standard library that gives 
you the lexographically next permutation of an array.

http://wordaligned.org/articles/next-permutation?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+wordaligned+(Word+Aligned)

Interesting. :-)

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Darren New wrote:

> Interesting. :-)

"while (!(*i < *--j)) {}"

Um, yeah, "interesting" would be the term I'd use. WTF? o_O



Personally, I'd do it this way:

nextP :: Ord x => [x] -> Maybe [x]
nextP []  = Nothing
nextP [x] = Nothing
nextP xs  =
   case split (reverse xs) of
     ([] , _  ) -> Nothing
     (ss', ps') ->
       let
         p0         = head ps'
         (ss0, ss1) = span (p0 >=) ss'
         s0         = head ss1
         ps         = reverse (s0 : tail ps')
         ss         = ss0 ++ [p0] ++ tail ss1
       in Just (ps ++ ss)

split :: Ord x => [x] -> ([x], [x])
split [] = ([], [])
split (x:xs) = work x xs
   where
     work x0 [] = ([x0], [])
     work x0 (x:xs)
       | x >= x0   = let (ys,zs) = work x xs in (x0:ys, zs)
       | otherwise = ([x0], x:xs)

Post a reply to this message

Invisible wrote:
> "while (!(*i < *--j)) {}"

C has always advocated piling up a bunch of side effects inside 
conditionals.   Even to the point where Google's go has completely useless 
syntax for doing so.

In go, you can write
   if x := y + 1; x > 5 { ... }

Which is always exactly precisely the same as
   x := y + 1;
   if x > 5 { ... }

Since you *always* need braces, and the result of evaluating the assignment 
isn't ever used as the conditional, it's just a way of embedding 
side-effects into a part of a statement that should be side-effect free, 
apparently because the people designing go are so used to C's actually 
*useful* side effects that they missed the result.

The above line could also be
   do { j -= 1; } while (*j <= *i);
(or maybe while *i < *j. I don't care to work it out for sure)

So, yeah, it's opaque C++ code there.


> Um, yeah, "interesting" would be the term I'd use. WTF? o_O

The algorithm is interesting, not the implementation.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Invisible wrote:
> > "while (!(*i < *--j)) {}"

> C has always advocated piling up a bunch of side effects inside 
> conditionals.

  OTOH, once you learn to read it, it's not that bad.

  It's a bit like using "++i" instead of "i = i + 1". The latter might be
clearer at first, but once you understand what "++i" means, not really.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Invisible wrote:
>>> "while (!(*i < *--j)) {}"
> 
>> C has always advocated piling up a bunch of side effects inside 
>> conditionals.
> 
>   OTOH, once you learn to read it, it's not that bad.

Not in moderation. If something in the condition can't easily be expressed 
outside the condition, it's helpful. For example,
   while (EOF != (c = getchar())) { ... }
You can't really put the assignment outside the condition without 
duplicating that code, and it's kind of an accident of the design of the 
libraries that means you can't find out the result from getchar without 
invoking undesirable side-effect.[1] But convolving the comparison and the 
decrement in this case was unnecessary, I think. Doing the decrement in the 
body would say "keep decrementing until the condition is satisfied", which 
doesn't really come across in the way it's written.

>   It's a bit like using "++i" instead of "i = i + 1". The latter might be
> clearer at first, but once you understand what "++i" means, not really.

You definitely have to look at that expression to figure out what it's 
doing. Of course, they could have reversed the letters and made it a little 
clearer, too.


[1] You don't have this problem with iterators, for example, as you can just 
as for "*j" as often as you want without changing "j".  Eiffel and Ada solve 
it by requiring/suggesting that anything that has side effects doesn't 
return a value. So in Eiffel, there's a (void) procedure to read the next 
character into a buffer inside the object, and a function to get whatever 
character was most recently read, so you don't need to do the assignment 
inside the condition to save the character it returned, the way you need to 
in non-OO C.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message

>     ([] , _  ) -> Nothing

Yeh, it's really clear what this line does to a non-Haskeller :-)

Post a reply to this message

scott wrote:
>>     ([] , _  ) -> Nothing
> 
> Yeh, it's really clear what this line does to a non-Haskeller :-)

I'll tell you what it does: It makes the function crash. o_O

It *should* in fact be

    (_  , [] ) -> Nothing

It seems I got my arguments the wrong way around. :-/

As for what it *means*, it means that if the prefix is empty ("[]"), 
there is no next permutation ("Nothing"). The "_" simply means that it 
doesn't matter what the suffix part is.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> scott wrote:
> >>     ([] , _  ) -> Nothing
> > 
> > Yeh, it's really clear what this line does to a non-Haskeller :-)

> I'll tell you what it does: It makes the function crash. o_O

  After this you should really stop picking on C variants (or at the very
least, not immediately compare them to Haskell). ;)

-- 
                                                          - Warp

Post a reply to this message

>>>>     ([] , _  ) -> Nothing
>>> Yeh, it's really clear what this line does to a non-Haskeller :-)
> 
>> I'll tell you what it does: It makes the function crash. o_O
> 
>   After this you should really stop picking on C variants (or at the very
> least, not immediately compare them to Haskell). ;)

Why? Because I wrote some code with a small typo?

Post a reply to this message

scott wrote:
>>     ([] , _  ) -> Nothing
> 
> Yeh, it's really clear what this line does to a non-Haskeller :-)

It's pretty standard notation for functional languages. Erlang uses the same 
notation. If you get a two-element tuple with the first element being an 
empty list, the result is an arbitrary atomic value (not unlike an "enum") 
called "Nothing".

It's no less clear than function calls or array indexes if you've ever used 
that operation before in a programming language. It's about as complex as a 
case statement.

-- 
Darren New, San Diego CA, USA (PST)
   Human nature dictates that toothpaste tubes spend
   much longer being almost empty than almost full.

Post a reply to this message