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