[Algorithm] Sets - Fisher–Yates shuffle - 하고싶은거하는

Fisher–Yates 셔플?

Fisher–Yates 셔플(또는 Knuth 셔플)은 유한한 배열이나 리스트의 무작위 순열을 생성하는 알고리즘입니다. 이 알고리즘은 리스트를 역순으로 반복하며 각 요소를 자신 또는 앞에 있는 임의의 요소와 교환하는 방식으로 작동합니다.

이 알고리즘은 편향되지 않은 무작위 셔플을 보장하는데, 이는 배열의 모든 가능한 순열이 동일한 확률로 발생한다는 것을 의미합니다. 시간 복잡도는 $ O(n) $으로 매우 효율적입니다.

Fisher–Yates 셔플의 단계

배열의 마지막 요소부터 시작합니다.
아직 섞이지 않은 배열의 부분에서 무작위로 요소를 선택합니다.
현재 요소와 선택된 요소를 교환합니다.
배열의 끝에서부터 처음까지 이 과정을 반복합니다.

Fisher–Yates 셔플의 사용 사례

카드 셔플: 게임이나 시뮬레이션에서 카드 덱이나 아이템 셋을 섞는 데 널리 사용됩니다.
무작위 샘플링: 데이터를 샘플링하기 전에 섞어 편향 없이 선택할 수 있도록 하는 데 사용됩니다.
무작위 알고리즘: Monte Carlo 방식과 같이 무작위 셔플이 필요한 알고리즘에서 활용됩니다.
엔터테인먼트와 게임: 비디오 게임에서 행동이나 이벤트 목록을 섞는 데 자주 사용됩니다.

JavaScript로 구현한 Fisher–Yates 셔플 예제

function fisherYatesShuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    // 0에서 i까지 무작위 인덱스 생성
    const j = Math.floor(Math.random() * (i + 1));
    // i와 j의 요소를 교환
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

// 사용 예시
const array = [1, 2, 3, 4, 5, 6];
console.log(fisherYatesShuffle(array));

설명:

반복문은 마지막 인덱스(arr.length - 1)에서 첫 번째 인덱스(0)까지 순회합니다.
각 인덱스에 대해 0에서 $ i $까지 무작위 인덱스 $ j $를 선택하고, $ i $와 $ j $의 요소를 교환합니다.

Rust로 구현한 Fisher–Yates 셔플 예제

Rust에서는 rand 크레이트를 사용하여 무작위 숫자를 생성합니다.

# Cargo.toml 파일에 추가
[dependencies]
rand = "0.8"

use rand::Rng;

fn fisher_yates_shuffle<T>(arr: &mut [T]) {
    let mut rng = rand::thread_rng();

    for i in (1..arr.len()).rev() {
        // 0에서 i까지 무작위 인덱스 생성
        let j = rng.gen_range(0..=i);
        // i와 j의 요소를 교환
        arr.swap(i, j);
    }
}

fn main() {
    let mut array = vec![1, 2, 3, 4, 5, 6];
    fisher_yates_shuffle(&mut array);
    println!("{:?}", array);
}

설명:

rand::thread_rng()는 무작위 숫자 생성기를 만듭니다.
rng.gen_range(0..=i)는 0에서 $ i $ 사이의 무작위 인덱스를 생성합니다.
arr.swap(i, j) 함수는 인덱스 $ i $와 $ j $의 요소를 교환합니다.

요약:

Fisher–Yates 셔플은 무작위 순서를 생성하는 간단하고 효율적인 알고리즘입니다. 주로 카드나 배열을 섞을 때 사용되며, 모든 순열이 동일한 확률로 발생하도록 보장합니다. JavaScript와 Rust에서는 유사한 논리를 사용해 요소를 무작위로 교환함으로써 셔플을 구현할 수 있습니다.

What is the Fisher–Yates Shuffle?

The Fisher–Yates shuffle (also known as the Knuth shuffle) is an algorithm for generating a random permutation of a finite sequence, typically an array or list. It works by iterating through the list in reverse order and swapping each element with a randomly selected element that comes before it (or with itself).

The algorithm guarantees an unbiased random shuffle, meaning each possible permutation of the list is equally likely. The time complexity is $ O(n) $, making it highly efficient for shuffling arrays.

Steps in the Fisher–Yates Shuffle

Start at the last element of the array.
Randomly pick an element from the portion of the array that hasn’t been shuffled yet.
Swap the current element with the randomly selected element.
Repeat the process, moving from the end of the array to the beginning.

Use Cases of Fisher–Yates Shuffle

Shuffling Cards: It’s widely used in games and simulations to shuffle a deck of cards or any set of items.
Random Sampling: Used in applications where you need to shuffle data before sampling, ensuring no bias in the selection process.
Randomized Algorithms: Many algorithms require random shuffling as part of their operations (e.g., Monte Carlo methods).
Entertainment and Games: Common in video games to shuffle lists of actions or events.

JavaScript Example for Fisher–Yates Shuffle

function fisherYatesShuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    // Generate a random index from 0 to i
    const j = Math.floor(Math.random() * (i + 1));
    // Swap elements at i and j
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

// Example usage
const array = [1, 2, 3, 4, 5, 6];
console.log(fisherYatesShuffle(array));

Explanation:

The loop goes from the last index (arr.length - 1) to the first (index 0).
For each index, it randomly selects an index $ j $ from 0 to $ i $, and swaps the elements at $ i $ and $ j $.

Rust Example for Fisher–Yates Shuffle

In Rust, we can use the rand crate for random number generation.

# Add this to your Cargo.toml file
[dependencies]
rand = "0.8"

use rand::Rng;

fn fisher_yates_shuffle<T>(arr: &mut [T]) {
    let mut rng = rand::thread_rng();

    for i in (1..arr.len()).rev() {
        // Generate a random index from 0 to i
        let j = rng.gen_range(0..=i);
        // Swap elements at i and j
        arr.swap(i, j);
    }
}

fn main() {
    let mut array = vec![1, 2, 3, 4, 5, 6];
    fisher_yates_shuffle(&mut array);
    println!("{:?}", array);
}

Explanation:

The rand::thread_rng() function creates a random number generator.
The rng.gen_range(0..=i) generates a random index from 0 to $ i $.
The arr.swap(i, j) function swaps the elements at indices $ i $ and $ j $.

Summary:

The Fisher–Yates shuffle is a simple yet efficient algorithm for generating random permutations of a list, commonly used for shuffling cards, arrays, or any data where a random order is desired. Both JavaScript and Rust implementations follow a similar logic of iterating through the array and swapping elements with randomly selected ones to ensure all permutations are equally likely.

[Algorithm] Sets - Fisher–Yates shuffle

집합 Fisher–Yates 셔플