ちょっとアルゴニズム - Shuffle(Swift)

raywenderlich/swift-algorithm-club

参考サイトをそのまま実行してもエラーが出るので少し修正してみます。

ひとつ目は、トランプようなのカードを一枚ずつ抜いて形で並び替えをする、抜くカードはランダムなので順序はバラバラになります。順番通りに並べるソートの逆の形になります。

extension Array {
 public mutating func shuffle() {
   var temp = [Element]()
   while !isEmpty {
       let i = Int.random(in: 0..<self.count)
       let obj = remove(at: i)
     temp.append(obj)
   }
   self = temp
 }
}

これをPlaygroundで実行します。

var list = [ "a", "b", "c", "d", "e", "f", "g" ]
list.shuffle()
list.shuffle()

["a", "b", "c", "d", "e", "f", "g"]
["f", "e", "b", "a", "c", "d", "g"]

と並び替えされます。

ポイントは

while !isEmpty {
let i = Int.random(in: 0..<self.count)
let obj = remove(at: i)
temp.append(obj)
}

の部分で、ランダムに選んだカードを最初の配列から取り除き

remove(at:i)

、新しい配列"temp"に入れていきます。

temp.append(obj)

ちなみに変更している箇所は

let i = Int.random(in: 0..<self.count)

次は Fisher-Yates / Knuth shuffleです。
これはFisher-Yates shuffle の改良版ということです。

配列の末尾の要素を入れ替えていきます。その交換する要素をランダムに選んでいくという方法です。

extension Array {
 　　public mutating func shuffle() {
   　　　for i in stride(from: count - 1, through: 1, by: -1) {
     　　　let j = Int.random(in: 0...i)
     　　　　if i != j {
       　　　self.swapAt(i, j)
     　　　　}
  　　 　}
 　　}
}

for i in stride(from: count - 1, through: 1, by: -1){}

で末尾から数値を取り出して、ランダムな数値と入れ替えます。

let j = Int.random(in: 0...i)
　self.swapAt(i, j)

これでランダムな数値とになります。

おまけです。引数に配列の数を入れてやると、その数の長さ分の配列をランダムな数字で作ってくれます。

public func shuffledArray(_ n: Int) -> [Int] {
 var a = [Int](repeating: 0, count: n)
 for i in 0..<n {
   let j = Int.random(in: 0...i)
   
   a[i] = a[j]
   a[j] = i
 }
 return a
}