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 caveat 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".
[UPDATE: It has been corrected on the website nayuki.io. The author personally wrote a thank you note to me confirming the error and rectifying it.]
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 complexity: O(n)
No comments:
Post a Comment