I wrote a Python version of std::next_permutation with bunches of output, 
and I see what it's doing now. It's really rather clever.

C++, Python, and sample output:
http://darren.s3.amazonaws.com/permutations.zip

There's a loop that finds the first in-order pair of numbers, working from 
back to front. That's the
   while (true) { ii = i; i--; ... }
part, which doesn't stop until *i<*ii or you run off the front of the sequence.

If you run off the front, then every pair of numbers is out of order, so you 
have the lexically highest permutation, so you say "all done".

Otherwise, having found the pair of numbers out of order, you then find a 
'j' bigger than 'i'. Swap those two, then reverse the list to the right of 'i'.

It's sort of like doing a bubble sort, except you only sort things to the 
right of the first out of order element, and then you reverse the right half 
again, just to keep it maximally unsorted at each step.

-- 
   Darren New, San Diego CA, USA (PST)
   There's no CD like OCD, there's no CD I knoooow!

Post a reply to this message