swiftでシャッフル関数

レンジ(0..<10)などのシーケンス型をシャッフルしたくなるときがあるので，ここにメモしておきます．
シャッフルの実装はTAOCPに載っていたアルゴリズムP¹を使います．

実装

func shuffle<T>(inout array: [T]) {
    for var j = array.count - 1; j > 0; j-- {
        var k = Int(arc4random_uniform(UInt32(j + 1))) // 0 <= k <= j
        swap(&array[k], &array[j])
    }
}

func shuffled<S: SequenceType>(source: S) -> [S.Generator.Element] {
    var copy = Array<S.Generator.Element>(source)
    shuffle(&copy)
    return copy
}

関数shuffleの中身は，そのまんまアルゴリズムPで（実はもうほんのちょっと最適化できる），入力配列を破壊しつつシャッフルします．
関数shuffledの方は，SequenceType型（配列とか文字列とかレンジ）の入力をとり（sortedのように）元の入力を破壊せずにシャッフル済みの新たな配列を返します．

使用例

var a = [0,1,2,3,4,5,6,7,8,9]
shuffle(&a)
println(a)                                    // [3,2,0,4,1,7,9,5,6,8]

println(shuffled(0..<10))                     // [5,9,7,8,3,1,0,2,4,6]

println(String(shuffled("Hello, World!")))    // l WeHdl!rloo,

---

1. D. E. Knuth, "The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition," pp.145 ↩