A simple algorithm from Wikipedia with C++ implementation (can be used in Permutations and Permutations II)


  • 118

    Well, in fact the problem of next permutation has been studied long ago. From the Wikipedia page, in the 14th century, a man named Narayana Pandita gives the following classic and yet quite simple algorithm (with minor modifications in notations to fit the problem statement):

    1. Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, the permutation is sorted in descending order, just reverse it to ascending order and we are done. For example, the next permutation of [3, 2, 1] is [1, 2, 3].
    2. Find the largest index l greater than k such that nums[k] < nums[l].
    3. Swap the value of nums[k] with that of nums[l].
    4. Reverse the sequence from nums[k + 1] up to and including the final element nums[nums.size() - 1].

    Quite simple, yeah? Now comes the following code, which is barely a translation.

    Well, a final note here, the above algorithm is indeed powerful --- it can handle the cases of duplicates! If you have tried the problems Permutations and Permutations II, then the following function is also useful. Both of Permutations and Permutations II can be solved easily using this function. Hints: sort nums in ascending order, add it to the result of all permutations and then repeatedly generate the next permutation and add it ... until we get back to the original sorted condition. If you want to learn more, please visit this solution and that solution.

    class Solution {
        void nextPermutation(vector<int>& nums) {
        	int k = -1;
        	for (int i = nums.size() - 2; i >= 0; i--) {
        		if (nums[i] < nums[i + 1]) {
        			k = i;
        			break;
        		}
        	} 
        	if (k == -1) {
        	    reverse(nums.begin(), nums.end());
        	    return;
        	}
        	int l = -1;
        	for (int i = nums.size() - 1; i > k; i--) {
        		if (nums[i] > nums[k]) {
        			l = i;
        			break;
        		} 
        	} 
        	swap(nums[k], nums[l]);
        	reverse(nums.begin() + k + 1, nums.end()); 
        }
    }; 
    

  • 0
    P

    Impresive algorithm, though it is 700 hundred year old! Do you know the reason for step 4?


  • 0

    Hi, peace. I really cannot give a clear-cut reason for that step. But I think it will become clear to you after running some examples :-)


  • 0
    C

    Hi jianchao.li.fighter, I have very similar code as yours but without the "return" below the reverse function. It works well in my compiler (xcode) but can't pass the leetcode check. Do you know or can you tell me why do you add the "return" there? Thanks.


  • 0

    Hi, clarkckl. Well, at that case (after reverse), the result is just the reversed nums and the remaining lines should not be executed, so we directly return. BTW, what problem do you meet on the LeetCode OJ: Wrong Answer, or Runtime Error?


  • 0
    C

    Hello jianchao.li.fighter, i got it. There's a runtime error. Last executed input: [1,2]


  • 0

    Yeah, clarkckl. In the case that nums is sorted, its next permutation is just its reverse.


  • 0
    C

    Okay. I think it's the compiler's problem. Thank you for the explanation!


  • 0

    Compiler problem? Well, if the code is not accepted by the OJ, that means it is the code that has bugs, instead of the compiler.


  • 0
    C

    but it works well in my testcases, the only difference is with/without the return. yeah but i think you're right.


  • 1
    J

    700 years...we are standing on the shoulder of the great giant!


  • 0
    L

    Hi peace, for step 4, the reason is that from nums[k + 1] to nums[nums.size() - 1] is must descending order (because if it's not, we can kind larger index at step 1). So we need to reverse it for the next generation.


  • 0
    T

    @peace Step 3 increases the prefix by the smallest possible amount, and Step 4 is needed to reset the suffix to the first permutation. See my solution and referenced explanation.


  • 2
    K

    Great explanation. I have the same idea, only for the actual implementation slightly simpler code.

    I guess it's noteworthy that the linear search step to find nums[i] > nums[k-1] can be replaced by binary search. In that way the overall complexity is still O(n) but it might slightly over-perform the simple solution in long sequences.

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            // Find from the smallest k such that nums[k - 1] < nums[k].
            int k;
            for (k = nums.size() - 1; k > 0 && nums[k - 1] >= nums[k]; k--);
            
            // k == 0 means the sequence itself is non-increasing. Reverse it.
            if (k > 0) {
                // Find the index i such that nums[i] > nums[k-1], i in [k, n-1].
                int i;
                for (i = nums.size() - 1; nums[i] <= nums[k - 1]; i--);
                
                swap(nums[k - 1], nums[i]);
            }
            reverse(nums.begin() + k, nums.end());
        }
    };
    

  • 0

    I have been searching for a while, what does the next permutation mean?

    It seams everyone knew it. :/

    I want to know how they define which permutation is the next permutation....


  • 0
    J

    Is there anyone who knows the reasoning behind this method?


  • 1
    S

    @peace .If you find k,the elements behind it must be in descending order(can be proofed by contradiction easily), similarly, the nums[l] must be the minimal element that bigger than nums[k] behind nums[k] . Since the elements behind k are in descending order,the next Permutation in position k must be nums[l],and the elements behind k are in ascending order after swap the value of nums[k] with that of nums[l].Again,since the elements behind k are in descending order(after swap is also right),so we need to reverse the sequence from nums[k + 1] up to and including the final element nums[nums.size() - 1].


  • 0
    S

    @peace .If you find k,the elements behind it must be in descending order(can be proofed by contradiction easily), similarly, the nums[l] must be the minimal element that bigger than nums[k] behind nums[k] .
    Since the elements behind k are in descending order,the next Permutation in position k must be nums[l],and the elements behind k are in ascending order after swap the value of nums[k] with that of nums[l].
    Again,since the elements behind k are in descending order(after swap is also right),so we need to reverse the sequence from nums[k + 1] up to and including the final element nums[nums.size() - 1].


  • 1

    I think another view to understand this solution is to draw the Tree, namely search space, of the permutation.
    The next permutation is actually the next leaf on the DFS path. Then it may be easier to review this solution:

    • Step-1: The internal node on the path that represents nums[0...k-1] is the LCA (Lowest Common Ancestor) of current permutation (leaf) and the next one we want.
    • Step-2: nums[0..k-1] + nums[l] is the child node of LCA that goes to next permutation.
    • Step-3: reverse all the remaining nums means we goes for the first leaf in this subtree.

    Hope I get it right and you know what I'm talking about...

    0_1482546585830_1773271831.jpg


  • 0
    P

    @peace I think it is because of the fact that all the numbers after K (K is the largest number which satisfies the property nums[k] < nums[k+1]) are bigger than the numbers on their right. Hence when we swap the two numbers in step 3, a smaller number is placed at index l. Hence by sorting from K+1 to L we get the lexicographic order.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.