Next Permutation

Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers.

If such arrangement is not possible, it must be rearranged as the lowest possible order i.e., sorted in an ascending order.

Note: The replacement must be in-place, do not allocate extra memory.

Examples:

Input:  n = 218765
Output: 251678

Input:  n = 1234
Output: 1243

Input: n = "4321"
Output: 1234

Input: n = "534976"
Output: "536479"

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

void Solution::nextPermutation(vector<int> &digits) { int i, size = digits.size(); for(i = size - 1; i > 0; i--){ if(digits[i] > digits[i - 1]){ break; } } //no such i found if(i == 0){ reverse(digits.begin(), digits.end()); return; } //find the smallest number greater than the smaller number found above int j = size - 1; while (digits[j] <= digits[i - 1]){ j--; } //swap the two numbers int t = digits[i - 1]; digits[i - 1] = digits[j]; digits[j] = t; //reverse after the ith position reverse(digits.begin() + i, digits.end()); }