|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |