Please check the comments in the code for the explanation. Let me know if you have any questions.
class Solution: # @param num, a list of integer # @return a list of integer def nextPermutation(self, num): if len(num)<2: return num ii,tmp=len(num)-2,[num[-1]] # Scan from back of the list to check the location that the first time the digit increase. This index would be recored as ii. At the same time, this non-increasing sublist would be recored in tmp. while ii>=0: if num[ii]>=num[ii+1]: tmp.append(num[ii]) else: break ii-=1 # if ii>=0: that means we got to rearrange the elements from ii to end. if ii>=0: jj=len(tmp) # check the smallest digit that is larget than num[ii]. And it would be the new head for this sublist. while jj>=1 and tmp[jj-1]>num[ii]: jj-=1 subHead=tmp[jj] tmp[jj]=num[ii] tmp.sort() res=num[0:ii]+[subHead]+tmp # if ii==-1, the list is in the reverse order ( the last permutation ). The solution shall be the reverse of the input. else: res=tmp return res