Swift3/Swift4实现Fisher–Yates洗牌算法随机打乱数组(shuffle)

时间:2022-06-01 12:59:44

添加两个extension:

  • 可变集合添加shuffle()方法,打乱原来集合的元素顺序
  • Sequence添加shuffled()方法,返回原序列乱序的数组

Swift 4

extension MutableCollection {
    /// 打乱集合里的元素
    mutating func shuffle() {
        let c = count
        guard c > 1 else { return }

        for (firstUnshuffled, unshuffledCount) in zip(indices, stride(from: c, to: 1, by: -1)) {
            let d: IndexDistance = numericCast(arc4random_uniform(numericCast(unshuffledCount)))
            let i = index(firstUnshuffled, offsetBy: d)
            swapAt(firstUnshuffled, i)
        }
    }
}

extension Sequence {
    /// 返回序列乱序的数组
    func shuffled() -> [Element] {
        var result = Array(self)
        result.shuffle()
        return result
    }
}

Swift 3

extension MutableCollection where Indices.Iterator.Element == Index {
    /// 打乱集合里的元素
    mutating func shuffle() {
        let c = count
        guard c > 1 else { return }

        for (firstUnshuffled , unshuffledCount) in zip(indices, stride(from: c, to: 1, by: -1)) {
            let d: IndexDistance = numericCast(arc4random_uniform(numericCast(unshuffledCount)))
            guard d != 0 else { continue }
            let i = index(firstUnshuffled, offsetBy: d)
            swap(&self[firstUnshuffled], &self[i])
        }
    }
}

extension Sequence {
    /// 返回序列乱序的数组
    func shuffled() -> [Iterator.Element] {
        var result = Array(self)
        result.shuffle()
        return result
    }
}

使用

let x = [1, 2, 3].shuffled()
// x == [2, 3, 1]

let fiveStrings = stride(from: 0, through: 100, by: 5).map(String.init).shuffled()
// fiveStrings == ["20", "45", "70", "30", ...]

var numbers = [1, 2, 3, 4]
numbers.shuffle()
// numbers == [3, 2, 1, 4]