1. 題目要求：

對(duì)于給定的可能有重復(fù)元素的數(shù)組，打印出所有數(shù)組中所有元素重新排列的所有可能的不同組合，不要求各個(gè)組合之間的順序
例如:
給出數(shù)組[1, 2]
打印結(jié)果：
1 2
2 1

2. 解題思路：

• 取出數(shù)組中的第一個(gè)元素
• 遞歸調(diào)用函數(shù)，將剩余元素進(jìn)行重排，返回值類型為嵌套的數(shù)組
• 將取出的元素插入到重排結(jié)果中的每一個(gè)數(shù)組中的每一個(gè)位置，依次生成本次遞歸返回的最終的元素組合之一
• 利用哈希算法去重后，將不重復(fù)的元素組合添加到最終要返回的數(shù)組中
• 關(guān)于去重的算法，可以利用Set中元素查找過程利用了哈希算法的特性，直接根據(jù)組合中的所有元素生成一個(gè)唯一不會(huì)重復(fù)的Key，放入Set中即可

進(jìn)一步探討：

• 若組合情況太多，可將上面的Key分成兩部分，構(gòu)成[Key1 : [key2]]雙散列(key2所在容器為Set)，以避免單個(gè)散列表過大，查找耗費(fèi)時(shí)間過長(zhǎng)的問題
• 若給定數(shù)組中的元素并非簡(jiǎn)單的Int類型，可將元素依據(jù)位置轉(zhuǎn)換成Int數(shù)組(新數(shù)組中的元素代表原數(shù)組中的對(duì)象的位置)，對(duì)于重復(fù)元素，Int值取該元素第一次出現(xiàn)的位置。 將得到的Int數(shù)組放入遞歸函數(shù)進(jìn)行重排，遞歸函數(shù)返回的排列組合為原數(shù)組中元素的位置索引，根據(jù)位置索引提取原數(shù)組中的元素進(jìn)行打印即可

3. Swift代碼

• 遞歸重排函數(shù)

func arrangeArray(array: [Int]) -> [[Int]]{
    //元素個(gè)數(shù)為0時(shí)返回空數(shù)組
    if array.count == 0 {
        return [[Int]]()
    }
    
    //初始化
    var finalArray: [[Int]] = [[Int]]()
    var hasRepeatNumber = false                 //是否需要去重
    for i in 0 ..< array.count {
        for j in i+1 ..< array.count {
            if array[i] == array[j] {
                hasRepeatNumber = true
                break
            }
        }
        if hasRepeatNumber {
            break
        }
    }
    
//    var hashTable = [String : Set<String>]()    //利用字典和Set實(shí)現(xiàn)雙散列查找
    var hashSet = Set<String>()                 //利用Set實(shí)現(xiàn)單散列查找

    
    //排列組合
    var tempArray = array
    let oneElement = tempArray.removeFirst()                //取出一個(gè)元素
    let returnedArray = arrangeArray(array: tempArray)     //剩余元素排列組合

    //將取出的元素插入到遞歸返回的數(shù)組中的每一個(gè)數(shù)組中的每一個(gè)位置，并添加到遞歸函數(shù)要返回的數(shù)組中
    if returnedArray.count == 0 {
        finalArray.append([oneElement])
    } else {
        for oneArray in returnedArray {
            for i in 0 ... oneArray.count {
                var newArray = oneArray
                newArray.insert(oneElement, at: i)

//                //雙散列去重后添加到finalArray中
//                if hasRepeatNumber {
//                    addNewArrayFilterByDict(hashTable: &hashTable, newArray: &newArray, finalArray: &finalArray)
//                } else {
//                    finalArray.append(newArray)
//                }

                //單散列去重后添加到finalArray中
                if hasRepeatNumber {
                    addNewArrayFilterBySet(hashSet: &hashSet, newArray: &newArray, finalArray: &finalArray)
                } else {
                    finalArray.append(newArray)
                }

            }
        }
    }

    return finalArray
}

private func addNewArrayFilterByDict(hashTable: inout [String : Set<String>], newArray: inout [Int], finalArray: inout [[Int]] ) -> Void {
    var hashKey1 = String()
    var hashKey2 = String()
    for j in 0 ..< newArray.count {
        if j % 2 == 0 {
            if newArray[j] > 9 {                                //此判斷對(duì)性能無明顯影響
                hashKey1 += " " + String(newArray[j]) + " "     //兩個(gè)相鄰的非個(gè)位數(shù)相鄰時(shí)多添加了一個(gè)空格，若增加一個(gè)末尾是否是空格的判斷，在非個(gè)位數(shù)占比較少時(shí)明顯增加運(yùn)算時(shí)間
            } else {
                hashKey1 += String(newArray[j])
            }
        } else {
            if newArray[j] > 9 {
                hashKey2 += " " + String(newArray[j]) + " "
            } else {
                hashKey2 += String(newArray[j])
            }
        }
    }
    
    if let set = hashTable[hashKey1] {
        //已經(jīng)有內(nèi)部哈希表進(jìn)行查找
        if set.contains(hashKey2) {
            //重復(fù)，丟棄
            
        } else {
            finalArray.append(newArray)
            hashTable[hashKey1]?.insert(hashKey2)
        }
    } else {
        //無內(nèi)部哈希表時(shí)添加內(nèi)部哈希表，注意字典為值類型
        finalArray.append(newArray)
        hashTable[hashKey1] = Set<String>()
        hashTable[hashKey1]?.insert(hashKey2)
    }

}

private func addNewArrayFilterBySet(hashSet: inout Set<String>, newArray: inout [Int], finalArray: inout [[Int]] ) -> Void {
    var hashKey = String()
    for element in newArray {
        if element > 9 {                                    //此判斷對(duì)性能無明顯影響
            hashKey += " " + String(element) + " "          //兩個(gè)相鄰的非個(gè)位數(shù)相鄰時(shí)多添加了一個(gè)空格，若增加一個(gè)末尾是否是空格的判斷，在非個(gè)位數(shù)占比較少時(shí)明顯增加運(yùn)算時(shí)間
        } else {
            hashKey += String(element)
        }
    }
    
    if hashSet.contains(hashKey) {
        //重復(fù)，丟棄
        
    } else {
        finalArray.append(newArray)
        hashSet.insert(hashKey)
    }
}

• 調(diào)用遞歸函數(shù)并打印結(jié)果

let array1 = [1, 2, 1, 2, 10, 2, 3, 2, 3, 10, 1, 1, 2, 1]       //雙散列查找去重需68s，單散列查找去重需74s
let array2 = [1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 1, 1, 2, 1]     //雙散列查找去重需21s，單散列查找去重需27s

let array3 = [1, 2, 3, 4, 5, 6, 4, 2, 3, 1, 2]
let array4 = [1, 2, 1, 2]

//print(Date())
let arrangedArray = arrangeArray(array: array4)
//print(Date())

//print(arrangedArray.count)

//遍歷數(shù)組并打印
for i in 0 ..< arrangedArray.count {
    //合成新的字符串
    let array = arrangedArray[i]

    var string = ""
    for j in 0 ..< array.count {
        if j == array.count - 1 {
            string += String(array[j])
        } else {
            string += String(array[j]) + " "
        }
    }
    //打印字符串
    print(string)
}

• 對(duì)于復(fù)雜類型數(shù)組可將元素的位置數(shù)組傳入遞歸函數(shù)進(jìn)行排列，然后再根據(jù)返回的位置索引進(jìn)行打印

let stringArray = ["沒", "Bug", "沒有", "Bug"]
var indexArray = [Int]()
for i in 0 ..< stringArray.count {
    let string = stringArray[i]
    let j = stringArray.index(of: string)!
    indexArray.append(j)
}

//print(indexArray)

let arrangedIndex = arrangeArray(array: indexArray)

//print(arrangedIndex.count)

for oneArray in arrangedIndex {
    var string = ""
    for i in 0 ..< oneArray.count {
        if i == oneArray.count {
            string += stringArray[oneArray[i]]
        } else {
            string += stringArray[oneArray[i]] + " "
        }
    }
    print(string)
}

歡迎留言討論。

GitHub代碼：https://github.com/luqz/ArrangeArrayDemo