Permutations · 數據結構與算法/leetcode/lintcode題解

# Permutations ### Source - leetcode: [Permutations | LeetCode OJ](https://leetcode.com/problems/permutations/) - lintcode: [(15) Permutations](http://www.lintcode.com/en/problem/permutations/) ### Problem Given a list of numbers, return all possible permutations. #### Example For nums = `[1,2,3]`, the permutations are: ~~~ [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] ~~~ #### Challenge Do it without recursion. ### 題解1 - Recursion(using subsets template) 排列常見的有數字全排列，字符串排列等。使用之前 [Subsets](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/subsets.html) 的模板，但是在取結果時只能取`list.size() == nums.size()`的解，且在添加list元素的時候需要注意除重以滿足全排列的要求。此題假設前提為輸入數據中無重復元素。 ### Python ~~~ class Solution: """ @param nums: A list of Integers. @return: A list of permutations. """ def permute(self, nums): alist = [] result = []; if not nums: return result self.helper(nums, alist, result) return result def helper(self, nums, alist, ret): if len(alist) == len(nums): # new object ret.append([] + alist) return for i, item in enumerate(nums): if item not in alist: alist.append(item) self.helper(nums, alist, ret) alist.pop() ~~~ ### C++ ~~~ class Solution { public: /** * @param nums: A list of integers. * @return: A list of permutations. */ vector<vector<int> > permute(vector<int> nums) { vector<vector<int> > result; if (nums.empty()) { return result; } vector<int> list; backTrack(result, list, nums); return result; } private: void backTrack(vector<vector<int> > &result, vector<int> &list, \ vector<int> &nums) { if (list.size() == nums.size()) { result.push_back(list); return; } for (int i = 0; i != nums.size(); ++i) { // remove the element belongs to list if (find(list.begin(), list.end(), nums[i]) != list.end()) { continue; } list.push_back(nums[i]); backTrack(result, list, nums); list.pop_back(); } } }; ~~~ ### Java ~~~ public class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) return result; List<Integer> list = new ArrayList<Integer>(); dfs(nums, list, result); return result; } private void dfs(int[] nums, List<Integer> list, List<List<Integer>> result) { if (list.size() == nums.length) { result.add(new ArrayList<Integer>(list)); return; } for (int i = 0; i < nums.length; i++) { if (list.contains(nums[i])) continue; list.add(nums[i]); dfs(nums, list, result); list.remove(list.size() - 1); } } } ~~~ ### 源碼分析在除重時使用了標準庫`find`(不可使用時間復雜度更低的`binary_search`，因為`list`中元素不一定有序)，時間復雜度為 O(N)O(N)O(N), 也可使用`hashmap`記錄`nums`中每個元素是否被添加到`list`中，這樣一來空間復雜度為 O(N)O(N)O(N), 查找的時間復雜度為 O(1)O(1)O(1). 在`list.size() == nums.size()`時，已經找到需要的解，及時`return`避免后面不必要的`for`循環調用開銷。使用回溯法解題的**關鍵在于如何確定正確解及排除不符條件的解(剪枝)**。 ### 復雜度分析以狀態數來分析，最終全排列個數應為 n!n!n!, 每個節點被遍歷的次數為 (n?1)!(n-1)!(n?1)!, 故節點共被遍歷的狀態數為 O(n!)O(n!)O(n!), 此為時間復雜度的下界，因為這里只算了合法條件下的遍歷狀態數。若不對 list 中是否包含 nums[i] 進行檢查，則總的狀態數應為 nnn^nnn 種。由于最終的排列結果中每個列表的長度都為 n, 各列表的相同元素并不共享，故時間復雜度的下界為 O(n?n!)O(n \cdot n!)O(n?n!), 上界為 n?nnn \cdot n^nn?nn. 實測`helper`中 for 循環的遍歷次數在 O(2n?n!)O(2n \cdot n!)O(2n?n!) 以下，注意這里的時間復雜度并不考慮查找列表里是否包含重復元素。 ### 題解2 - Recursion 與題解1基于 subsets 的模板不同，這里我們直接從全排列的數學定義本身出發，要求給定數組的全排列，可將其模擬為某個袋子里有編號為1到 n 的球，將其放入 n 個不同的盒子怎么放？基本思路就是從袋子里逐個拿球放入盒子，直到袋子里的球拿完為止，拿完時即為一種放法。 ### Python ~~~ class Solution: # @param {integer[]} nums # @return {integer[][]} def permute(self, nums): if nums is None: return [[]] elif len(nums) <= 1: return [nums] result = [] for i, item in enumerate(nums): for p in self.permute(nums[:i] + nums[i + 1:]): result.append(p + [item]) return result ~~~ ### C++ ~~~ class Solution { public: /** * @param nums: A list of integers. * @return: A list of permutations. */ vector<vector<int> > permute(vector<int>& nums) { vector<vector<int> > result; if (nums.size() == 1) { result.push_back(nums); return result; } for (int i = 0; i < nums.size(); ++i) { vector<int> nums_new = nums; nums_new.erase(nums_new.begin() + i); vector<vector<int> > res_tmp = permute(nums_new); for (int j = 0; j < res_tmp.size(); ++j) { vector<int> temp = res_tmp[j]; temp.push_back(nums[i]); result.push_back(temp); } } return result; } }; ~~~ ### Java ~~~ public class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); List<Integer> numsList = new ArrayList<Integer>(); if (nums == null) { return result; } else { // convert int[] to List<Integer> for (int item : nums) numsList.add(item); } if (nums.length <= 1) { result.add(numsList); return result; } for (int i = 0; i < nums.length; i++) { int[] numsNew = new int[nums.length - 1]; System.arraycopy(nums, 0, numsNew, 0, i); System.arraycopy(nums, i + 1, numsNew, i, nums.length - i - 1); List<List<Integer>> resTemp = permute(numsNew); for (List<Integer> temp : resTemp) { temp.add(nums[i]); result.add(temp); } } return result; } } ~~~ ### 源碼分析 Python 中使用`len()`時需要防止`None`, 遞歸終止條件為數組中僅剩一個元素或者為空，否則遍歷`nums`數組，取出第`i`個元素并將其加入至最終結果。`nums[:i] + nums[i + 1:]`即為去掉第`i`個元素后的新列表。 Java 中 ArrayList 和 List 的類型轉換需要特別注意。 ### 復雜度分析由于取的結果都是最終結果，無需去重判斷，故時間復雜度為 O(n!)O(n!)O(n!), 但是由于`nums[:i] + nums[i + 1:]`會產生新的列表，實際運行會比第一種方法慢不少。 ### 題解3 - Iteration 遞歸版的程序比較簡單，咱們來個迭代的實現。非遞歸版的實現也有好幾種，這里基于 C++ STL 中`next_permutation`的字典序實現方法。參考 Wikipedia 上的字典序算法，大致步驟如下： 1. 從后往前尋找索引滿足 `a[k] < a[k + 1]`, 如果此條件不滿足，則說明已遍歷到最后一個。 1. 從后往前遍歷，找到第一個比`a[k]`大的數`a[l]`, 即`a[k] < a[l]`. 1. 交換`a[k]`與`a[l]`. 1. 反轉`k + 1 ~ n`之間的元素。 ### Python ~~~ class Solution: # @param {integer[]} nums # @return {integer[][]} def permute(self, nums): if nums is None: return [[]] elif len(nums) <= 1: return [nums] # sort nums first nums.sort() result = [] while True: result.append([] + nums) # step1: find nums[i] < nums[i + 1], Loop backwards i = 0 for i in xrange(len(nums) - 2, -1, -1): if nums[i] < nums[i + 1]: break elif i == 0: return result # step2: find nums[i] < nums[j], Loop backwards j = 0 for j in xrange(len(nums) - 1, i, -1): if nums[i] < nums[j]: break # step3: swap betwenn nums[i] and nums[j] nums[i], nums[j] = nums[j], nums[i] # step4: reverse between [i + 1, n - 1] nums[i + 1:len(nums)] = nums[len(nums) - 1:i:-1] return result ~~~ ### C++ ~~~ class Solution { public: /** * @param nums: A list of integers. * @return: A list of permutations. */ vector<vector<int> > permute(vector<int>& nums) { vector<vector<int> > result; if (nums.empty() || nums.size() <= 1) { result.push_back(nums); return result; } // sort nums first sort(nums.begin(), nums.end()); for (;;) { result.push_back(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) { return result; } } // 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[j]; nums[j] = nums[i]; nums[i] = temp; // step4: reverse between [i + 1, n - 1] reverse(nums, i + 1, nums.size() - 1); } return result; } 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 { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) return result; Arrays.sort(nums); while (true) { // step0: add nums into result List<Integer> list = new ArrayList<Integer>(); for (int i : nums) { list.add(i); } result.add(list); // step2: find the first nums[k] < nums[k + 1] from the end to start int k = -1; for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { k = i; break; } } if (k == -1) break; // step3: find the first nums[l] > nums[k] from the end to start int l = nums.length - 1; while (nums[l] <= nums[k]) { l--; } // step3: swap between l and k int temp = nums[l]; nums[l] = nums[k]; nums[k] = temp; // step4: reverse between k + 1, nums.length - 1 reverse(nums, k + 1, nums.length - 1); } return result; } private void reverse(int[] nums, int lb, int ub) { while (lb < ub) { int temp = nums[lb]; nums[lb] = nums[ub]; nums[ub] = temp; lb++; ub--; } } } ~~~ ### 源碼分析注意好步驟即可，其中對于數組的 reverse 操作不可在 while 循環中自增，極易出 bug! 對于 Java 來說其實可以首先將數組轉化為 List, 相應的方法多一些。 ### 復雜度分析除了將 n!n!n! 個元素添加至最終結果外，首先對元素排序，時間復雜度近似為 O(nlogn)O(n \log n)O(nlogn), 反轉操作近似為 O(n)O(n)O(n), 故總的時間復雜度為 O(n!)O(n!)O(n!). 除了保存結果的`result`外，其他空間可忽略不計，所以此題用生成器來實現較為高效，擴展題可見底下的 Python itertools 中的實現，從 n 個元素中選出 m 個進行全排列。 ### Reference - [Permutation Generation](#) - Robert Sedgewick 的大作，總結了諸多 Permutation 的產生方法。 - [Next lexicographical permutation algorithm](http://www.nayuki.io/page/next-lexicographical-permutation-algorithm) - 此題非遞歸方法更為詳細的解釋。 - [Permutation - Wikipedia, the free encyclopedia](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) - 字典序實現。 - [Programming Interview Questions 11: All Permutations of String | Arden DertatArden Dertat](http://www.ardendertat.com/2011/10/28/programming-interview-questions-11-all-permutations-of-string/) - [algorithm - complexity of recursive string permutation function - Stack Overflow](http://stackoverflow.com/questions/5363619/complexity-of-recursive-string-permutation-function) - [[leetcode]Permutations @ Python - 南郭子綦 - 博客園](http://www.cnblogs.com/zuoyuan/p/3758816.html) - [[leetcode] permutations的討論 - tuantuanls的專欄 - 博客頻道 - CSDN.NET](http://blog.csdn.net/tuantuanls/article/details/8717262) - [非遞歸排列算法（Permutation Generation）](http://arieshout.me/2012/04/non-recursive-permutation-generation.html) - [閑談permutations | HelloYou](http://helloyou2012.me/?p=133) - [9.7. itertools — Functions creating iterators for efficient looping — Python 2.7.10 documentation](https://docs.python.org/2/library/itertools.html#itertools.permutations)