[Swift] Array의 shuffle() 메서드 (Fisher-Yates 알고리즘)

Swift Array’s Shuffle()

스위프트 배열에는 요소들을 뒤섞어주는 shuffle() 메서드가 존재합니다.

var names = ["Alejandro", "Camila", "Diego", "Luciana", "Luis", "Sofía"]
names.shuffle()
// names == ["Luis", "Camila", "Luciana", "Sofía", "Alejandro", "Diego"]

공식 문서에서는 RandomAccessCollection 프로토콜을 채택한 인스턴스가 사용할 수 있다고 합니다.

WWDC 2018에서, 이런 셔플 알고리즘은 Fisher-Yates 알고리즘을 사용해 구현했다고 합니다.

https://developer.apple.com/videos/play/wwdc2018/406/?time=1289

(동영상 "Fisher–Yates shuffle" 부분은 23:05 ~ )

Fisher-Yates 알고리즘의 최초 방법

피셔-예이츠 셔플 알고리즘은 커누스 셔플이라고도 하는데, 최초의 방법은 다음과 같은 방법입니다.

1. 1부터 N까지의 수를 일단 쓴다.

2. 1과 지워지지 않고 남은 수의 개수 사이의 임의의 수 k를 선택한다.

3. 작은 쪽부터 세어 아직 지워지지 않은 k 번째 수를 지워서 별도의 목록 끝에 적어둔다.

4. 모든 수가 지워질 때까지 2단계부터 반복한다.

5. 3단계에서 기록한 일련의 수가 임의 순열이 된다.

2단계에서 선택한 임의의 수가 실제 난수이며, 편항되지 않은 경우에 결과도 편향되지 않는다고 합니다. 그래서 난수표에서 원하는 범위위 편향되지 않는 난수를 얻는 방법을 중요하게 설명했다고 합니다.

현대적인 알고리즘

컴퓨터용으로 더스텐펠드와 도널드 커누스가 알고리즘 셔플링으로 소개하여 알려지게 되었습니다. 최초 방법과 비슷하지만 조금은 달라졌는데, 만약 위 방법을 그대로 구현한다면 3단계에서 나머지 숫자를 계산하는데 불필요한 시간이 소비되지만, 더스텐펠드는 선택된 숫자를 각각의 마지막으로 지워지지 않은 숫자로 교체하여 목록의 끝으로 이동시키는 것을 반복되게 했습니다. 이렇게 되면 시간 복잡도가 O(n^2)에서 O(n)으로 낮출 수 있습니다.

위키백과에서 가져온 이미지입니다. 차례대로 단계에 따라 설명해보겠습니다.

1. 1부터 N까지를 일단 쓴다.

E, L, V, I, S

2. 지워지지 않고 남은 수 개수 사이의 임의의 수 k를 선택한다.

   → 처음에 5가 선택되었다고 예시에서는 가정했고, 결과적으로 S가 선택됩니다.

3. 선택된 요소를 마지막으로 지워지지 않은 요소로 교체하고, 목록의 끝으로 이동시킵니다.

   → 선택된 요소는 5이고, 마찬가지로 마지막으로 지워지지 않은 요소도 끝인 5이므로 결과적으로 제자리 이동이 됩니다. 변화가 없습니다.

4. 모든 수가 지워질 때 까지 2단계 부터 반복한다.
   1. 1과 지워지지 않은 수 1~4 까지의 수중 1을 선택했다고 가정합니다.
   2. 선택된 요소 1을 마지막으로 지워지지 않은 요소 4와 교체하고, 목록의 끝으로 이동시킵니다.

   I, L, V, E, S

   c. 범위를 줄이면서 반복합니다….

이 알고리즘을 의사코드로 표현해 본다면

for i from n-1 downto 1 do 
  // 0 ~ i 사이의 임의의 정수 j
  a[j] 와 a[i] 교환

배열을 반대 방향으로 섞는 동작을 알고리즘은 다음과 같이 표현할 수 있습니다.

for i from 0 to n−2 do
     // i ~ n-1 인 임의의 정수 j
     a[i]와 a[j] 교환

스위프트로 표현해 본다면

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

반대 방향 섞는 알고리즘은

extension Array {
  mutating func shuffle() {
    for i in 1..<count {
      let j = Int.random(in: 0...i)
      if i != j {
        swap(&self[i], &self[j])
      }
    }
  }
}

WWDC에서는 Swift에서 이와 같이 반대로 섞는 동작의 알고리즘을 사용한다고 합니다.

arc4random_uniform 함수는 UInt32를 인자로 받아서, 0부터 해당 인자까지 사이의 난수를 리턴합니다.

피셔 에이츠 알고리즘과 비슷한 알고리즘은 사톨로 알고리즘(Sattolo Algorithm)인데 둘의 차이점은 사톨로 알고리즘의 경우 2단계에서 난수를 1과 i-1 범위에서 선택한다는 점입니다. 이 경우 결과값이 항상 단일 주기로 구성되도록 되어 결과가 편향된다고 합니다.

출처: https://ko.wikipedia.org/wiki/피셔-예이츠_셔플

Uploaded by N2T