Describe an algorithm (and/or write the code) to generate the "next" permutation for a given permutation.

Define the "next" permutation as the smallest number larger than the current number where a number is composed of the elements of the array written from left to right.

E.g., here are the a few permutations in sequence:

[tt]

1,2,3,4,5 (first)

1,2,3,5,4

1,2,4,3,5

1,2,4,5,3

1,2,5,3,4

:

:

1,5,4,3,2

2,1,3,4,5

:

:

5,4,3,2,1 (last)

[/tt]

(Starting with 1,2,3,4,5 the application of the algorithm 119 times (in a loop) would generate all possible permutations.)