Wednesday, October 11, 2017

[Problem2 SPOJ-JNEXT] Next Lexicographical Permutation Algorithm; Ad-Hoc

PROBLEM: http://www.spoj.com/problems/JNEXT/

I was solving SPOJ-JNEXT, and from the comments section I came across this page:

https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

Nice explanation but there's a caveats to keep in mind to understand the working better-

It mentions:
If there is no such element – i.e. the entire sequence is non-decreasing – then this is already the last permutation.
It should rather be "non-increasing" instead of "non-decreasing".


My approach to solving this problem was similar so I won't bore you with another copy of how the algorithm works here: you may use the explanation in nayuki.io link above (with the correction in mind).

SOLUTION: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-JNEXT.cpp
Tested and accepted: http://www.spoj.com/status/JNEXT,chandniverma/

Time Complexity of get_next_perm() in worst case: O(n) where n is the number of digits in each test case in the input.
Space required: O(n)