Next Permutation

Next Permutation

Problem Statement

Given a permutation M, return the next permutation.

Problem Solving 

•  In this problem, the first thing that clicks is to observe examples. 
• And after multiple attempts, I started seeing a pattern. 
• First of all we need to see if there is a next permutation. If the sequence is already in the descending order then there is no need to work on it. 
• So starting from the last element we need to find the first element in reverse order which is out of order. 
• Post that since we need the next permutation and the next permutation should only involve the element at the least place value. That means that we have to work with the element just next to the element that is found earlier. 
• Now we need to find an element in the range to swap it with. This came after a long time that the max element smaller than the eligible element should be swapped. 
• Here we can optimize since to find such a element in an already sorted array is a eay task. 
• Post swapping the new range should be sorted. But recalling that this sequence is already sorted we can just reverse it instead of sorting it. 
• The solution works but it took lot of time to figure out. 
• Find code here. 

Learning

• Doing examples is also frustrating emotionally until you let go of fear that you can do this. Doing these problems is raising confidence every day. I feel proud and confident. 
• Simple edge cases and off by error are really the take away. 
• Also reverse iterator to forward iterator = reviterator.base(0 but this is risky as it has a convoluted meaning.  
• I need to understand upper bound and lower bound as well as these are also confusing sometimes. 
• Overall the problem was solved and this time I paid attention to code writting it as consice as possible. 
• Also this time I first wrote it on paper and then on pc. 
• Altogether good, I am feeling the benefits of writing and pursuing this exercise.