# Next Permutation ### Source - lintcode: [(52) Next Permutation](http://www.lintcode.com/en/problem/next-permutation/) ~~~ Given a list of integers, which denote a permutation. Find the next permutation in ascending order. Example For [1,3,2,3], the next permutation is [1,3,3,2] For [4,3,2,1], the next permutation is [1,2,3,4] Note The list may contains duplicate integers. ~~~ ### 題解 找下一個升序排列，C++ STL 源碼剖析一書中有提及，[Permutations](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/permutations.html) 一小節中也有詳細介紹，下面簡要介紹一下字典序算法： 1. 從后往前尋找索引滿足 `a[k] < a[k + 1]`, 如果此條件不滿足，則說明已遍歷到最后一個。 1. 從后往前遍歷，找到第一個比`a[k]`大的數`a[l]`, 即`a[k] < a[l]`. 1. 交換`a[k]`與`a[l]`. 1. 反轉`k + 1 ~ n`之間的元素。 由于這道題中規定對于`[4,3,2,1]`, 輸出為`[1,2,3,4]`, 故在第一步稍加處理即可。 ### Python ~~~ class Solution: # @param num : a list of integer # @return : a list of integer def nextPermutation(self, num): if num is None or len(num) <= 1: return num # step1: find nums[i] < nums[i + 1], Loop backwards i = 0 for i in xrange(len(num) - 2, -1, -1): if num[i] < num[i + 1]: break elif i == 0: # reverse nums if reach maximum num = num[::-1] return num # step2: find nums[i] < nums[j], Loop backwards j = 0 for j in xrange(len(num) - 1, i, -1): if num[i] < num[j]: break # step3: swap betwenn nums[i] and nums[j] num[i], num[j] = num[j], num[i] # step4: reverse between [i + 1, n - 1] num[i + 1:len(num)] = num[len(num) - 1:i:-1] return num ~~~ ### C++ ~~~ class Solution { public: /** * @param nums: An array of integers * @return: An array of integers that's next permuation */ vector<int> nextPermutation(vector<int> &nums) { if (nums.empty() || nums.size() <= 1) { return nums; } // step1: find nums[i] < nums[i + 1] int i = 0; for (i = nums.size() - 2; i >= 0; --i) { if (nums[i] < nums[i + 1]) { break; } else if (0 == i) { // reverse nums if reach maximum reverse(nums, 0, nums.size() - 1); return nums; } } // step2: find nums[i] < nums[j] int j = 0; for (j = nums.size() - 1; j > i; --j) { if (nums[i] < nums[j]) break; } // step3: swap betwenn nums[i] and nums[j] int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; // step4: reverse between [i + 1, n - 1] reverse(nums, i + 1, nums.size() - 1); return nums; } private: void reverse(vector<int>& nums, int start, int end) { for (int i = start, j = end; i < j; ++i, --j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } }; ~~~ ### Java ~~~ public class Solution { /** * @param nums: an array of integers * @return: return nums in-place */ public int[] nextPermutation(int[] nums) { if (nums == null || nums.length <= 1) { return nums; } // step1: find nums[i] < nums[i + 1] int i = 0; for (i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { break; } else if (i == 0) { // reverse nums if reach maximum reverse(nums, 0, nums.length - 1); return nums; } } // step2: find nums[i] < nums[j] int j = 0; for (j = nums.length - 1; j > i; j--) { if (nums[i] < nums[j]) { break; } } // step3: swap betwenn nums[i] and nums[j] int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; // step4: reverse between [i + 1, n - 1] reverse(nums, i + 1, nums.length - 1); return nums; } private void reverse(int[] nums, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } } ~~~ ### 源碼分析 和 Permutation 一小節類似，這里只需要注意在step 1中`i == 0`時需要反轉之以獲得最小的序列。對于有重復元素，只要在 step1和 step2中判斷元素大小時不取等號即可。 ### 復雜度分析 最壞情況下，遍歷兩次原數組，反轉一次數組，時間復雜度為 O(n)O(n)O(n), 使用了 temp 臨時變量，空間復雜度可認為是 O(1)O(1)O(1). ### Reference - [Permutations](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/permutations.html)