Swift版全排列-Heap's Algorithm

Swift 全排列算法，递归版和非递归版，都有！ 参考于Wiki-Heap's algorithm

很有Swift特色，不是简单的翻译而已，废话不多说，直接上代码（Swift3+）：

import Foundation

/// 递归全排列
func heapsAlgorithmPermutationRecursive<T: Collection>(list: T) -> [[T.Iterator.Element]] {
    var result: [[T.Iterator.Element]] = []
    var temp = Array(list)
    // Heap's Algorithm recursive
    func heap(n: Int) {
        if n == 1 {
            result.append(temp)
        }else {
            for i in 0..<n-1 {
                heap(n: n-1)
                swap(&temp[n%2 == 0 ? i : 0],&temp[n-1])
            }
            heap(n: n-1)
        }
    }
    // start
    heap(n: temp.count)
    return result
}

/// 非递归全排列
func heapsAlgorithmPermutationNonRecursive<T: Collection>(list: T) -> [[T.Iterator.Element]] {
    var result: [[T.Iterator.Element]] = []
    var temp = Array(list)
    var index = [Int](repeating: 0,count: temp.count)
    var i = 0
    // Heap's Algorithm non-recursive
    result.append(temp)
    while i < temp.count {
        if index[i] < i {
            swap(&temp[i%2 == 0 ? 0 : index[i]],&temp[i])
            result.append(temp)
            index[i] += 1
            i = 0
        }else {
            index[i] = 0
            i += 1
        }
    }
    return result
}


// 测试数据
//let list = Array(1...7)
var list = "abc".characters
var date = NSDate()
var result: [[Any]]

// 递归
result = heapsAlgorithmPermutationRecursive(list: list)
print("递归:ncount:(result.count)n耗时:(date.timeIntervalSinceNow)")
print(result)

// 非递归
date = NSDate()
result = heapsAlgorithmPermutationNonRecursive(list: list)
print(date.timeIntervalSinceNow)
print("非递归:ncount:(result.count)n耗时:(date.timeIntervalSinceNow)")
print(result)


// 去重测试
list = "abb".characters
result = heapsAlgorithmPermutationNonRecursive(list: list)
print("未去重前结果:n(result)")

let combine = result.flatMap { (c) -> String in
    let r = c as! [Character]
    return r.reduce("") {a,b in
        a + String(b)
    }
}
let norepeat = Set(combine)
print("去重后:n(norepeat)")

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!