배열 섞기

Array Shuffle Algoriothm

---

배경

유저 대상 설문조사 기능을 개발하면서, 질문에 대한 응답 선택지를 무작위로 섞는 기능이 요구사항에 있었다.
이왕이면 팀원들도 나중에 사용하도록 유틸로 개발하기 위해서 해당 기능을 개발하기 위해서 무작위 알고리즘에 대해 공부하게 되었다.
설문조사의 선택지들은 배열 형태이고, 이를 무작위의 순서로 보여주기 위해서는 각 선택지(원소)의 순서를 재배치했다.
이와 같은 문제에서 사용하는 무작위 알고리즘은 대표적으로 다음과 같은 것들이 있다.
1. Fisher-Yates Shuffle
2. Knuth Shuffle
3. Sattlo Shuffle

---

Fisher-Yates Shuffle

• 배열에서 무작위로 원소 하나를 선택한다.
• 선택한 원소를 제외한 나머지 원소의 개수를 세고, 선택한 원소를 새 배열에 옮긴다.
• 모든 원소가 새 배열로 옮겨질 때 까지 1, 2 과정을 반복한다.
• 원래 배열에서 모든 원소가 사라지면, 새로운 배열은 무작위로 나열된 배열이 된다.
• 해당 알고리즘은 원소가 편향되지 않게(동일한 확률) 새로운 무작위 배열을 생성한다.
• 단, 시간 복잡도가 O(n^2) 이다.
  • 매 반복마다 원래 배열에 남은 원소의 개수를 세는 과정이 필요하다 → O(n)
  • 무작위 원소를 선택하는 과정이 원소의 개수에 비례한다 → O(n)

---

Knuth Shuffle

• Fisher-Yates Shuffle을 개선한 알고리즘이다.
• 각 반복마다 남은 원소의 개수를 셀 필요가 없다 → O(n)
• 별도의 배열을 사용하지 않기 때문에 메모리 공간을 아낄 수 있다.
• 배열의 시작(혹은 마지막)에서 한 자리씩 이동하면서 각 자리에 들어갈 원소를 무작위로 선정한다.
• 이동한 자리를 포함하여 아직 자리가 새롭게 배정되지 않은 원소들을 무작위 원소 대상으로 한다.
• 자리가 새롭게 배정된 원소를 배제하면서, 절차를 진행할수록 무작위 원소 대상이 줄어든다.
• 무작위 선정 함수가 O(1) 이라면, 전체 알고리즘의 복잡도는 O(n) 이 된다.

// golang
func SliceShuffle[T any](slice []T) {
	for i := len(slice) - 1; i > 0; i-- { 
		j := rand.Intn(i + 1) // 0 <= j <= i 
		slice[i], slice[j] = slice[j], slice[i]
	}
}

---

Sattolo Shuffle(Sattlo Cycle)

• Knuth Shuffle을 변형한 알고리즘이다.
• Knuth Shuffle은 무작위 원소를 선정하고 새로운 자리를 배정할 때, 자리가 변경되지 않을 수 있다.
  (제자리 유지)
• Sattolo Shuffle은 무작위 원소의 자리를 선정할 때, 제자리를 배제한다.

//golang
func SliceShuffle[T any](slice []T){
    for i := len(slice) - 1; i > 0; i -- {
        j := rand.Intn(i) // 0 <= j < i
        slice[i], slice[j] = slice[j] , slice[i]
    }
}

---

결론

Knuth Shuffle 이나 Sattlo Shuffle은 거의 같은거 같고, 제자리를 배제해야 하는 필요가 있을때 Sattlo Shuffle을 사용하면 될 것 같다고 생각하고 함수를 만든 순간...

go rand 패키지 안에 rand.Shuffle 이라는 함수가 있는걸 알았다...😂

내장 패키지부터 살펴보자... 🙏🙏