數(shù)組全排列問題
題目：
給定一個數(shù)組，打印出數(shù)組的所有排列。比如數(shù)組為[1, 2, 3]，那最終輸出為：
[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]
就是把數(shù)組的所有順序的可能都輸出出來。
解題思路
1、遞歸解法
思路
遞歸的主旨思想就是把問題轉(zhuǎn)化成一個或幾個更小規(guī)模的子問題，比如說[1, 2, 3]的全排列不好處理，那我們固定第一位是1，然后求[2, 3]的全排列，然后再把第一位固定為2，求[1, 3]的全排列，最后把第一位固定成3，求[1, 2]的全排列。這樣，經(jīng)過層層推演，可以把題目轉(zhuǎn)換成求長度為1的數(shù)組的全排列，很顯然就得到答案了。
進一步解析
上面的思想是基本沒什么問題的，但是怎么實現(xiàn)固定第一位呢，這里有個比較巧妙的方法，就是讓第一位分別和后面幾位進行交換，這樣每個數(shù)字都會被固定在第一位一次，然后遞歸進行后面的操作，注意為了復(fù)用當前的數(shù)組，而不是每次都進行值拷貝，每次遞歸執(zhí)行完了，要把之前的順序換回來，這樣就確保了一個父問題處理多個子問題的時候不會因為某個子問題改變了數(shù)組順序，而無法處理下一個子問題了，具體來看下代碼：
// 遞歸函數(shù)function _allSort(arr, start, len) {// arr: 要全排列的數(shù)組，start: 從數(shù)組的start位置之后開始全排列，len: 數(shù)組總長度for (let i = start; i < len; i++) {if (start == len - 1) {// 如果當前全排列已經(jīng)是最后一位了，則輸出數(shù)組console.log(arr)} else {// 將start位置與各個位置交換swap(i, start, arr)// 交換完start自增1，處理子問題_allSort(arr, start + 1, len)// 交換完再換回來，確保每個子問題執(zhí)行完，不影響父問題的順序swap(start, i, arr)}}}// 位置交換function swap (a, b, nums) {let temp = nums[a]nums[a] = nums[b]nums[b] = temp}// 從0位置開始全排列function allSort(arr) {let start = 0let len = arr.length_allSort(arr, start, len)}allSort([1,2,3])
存在重復(fù)的問題
上面的代碼，在數(shù)組沒有重復(fù)元素的時候運行是正常的，但是一旦有重復(fù)就會出現(xiàn)一些小問題，我們看下arr為[1, 2, 2]的執(zhí)行結(jié)果：
[1, 2, 2][1, 2, 2][2, 1, 2][2, 2, 1][2, 2, 1][2, 1, 2]
發(fā)現(xiàn)沒，有一些組合是重復(fù)的，針對這些情況，需要做一些過濾，拿[1, 2, 2]進行舉例，當1和第一個2交換時正常交換，但是當1和第二個2交換的時候就要判定之前之前有沒有和2交換過，基于此我們升級一下代碼：
// 遞歸函數(shù)function _allSort(arr, start, len) {// arr: 要全排列的數(shù)組，start: 從數(shù)組的start位置之后開始全排列，len: 數(shù)組總長度for (let i = start; i < len; i++) {if (start == len - 1) {// 如果當前全排列已經(jīng)是最后一位了，則輸出數(shù)組console.log(arr)} else {// 判定當前元素是否重復(fù)出現(xiàn)let is_mutil = falsefor (let j = start; j < i; j++) {if (arr[j] === arr[i]) {console.log(arr[j], arr[i])is_mutil = truebreak}}if (is_mutil) {// 如果已經(jīng)出現(xiàn)過，就不在生成新的子問題了continue}// 將start位置與各個位置交換swap(i, start, arr)// 交換完start自增1，處理子問題_allSort(arr, start + 1, len)// 交換完再換回來，確保每個子問題執(zhí)行完，不影響父問題的順序swap(start, i, arr)}}}// 位置交換function swap (a, b, nums) {let temp = nums[a]nums[a] = nums[b]nums[b] = temp}// 從0位置開始全排列function allSort(arr) {let start = 0let len = arr.length_allSort(arr, start, len)}allSort([1,2,2])
這樣就成功解決了有重復(fù)數(shù)據(jù)的問題，不過同時也提升了時間復(fù)雜度。