Fisher-Yates Shuffle - 배열을 랜덤하게 섞기

// ❌ 잘못된 방법 (편향 발생!)
arr.sort(() => Math.random() - 0.5);

// ✅ 올바른 방법 (Fisher-Yates)
fisherYatesShuffle(arr);

// 잘못된 셔플: 특정 순열이 더 자주 나옴
const wrong = () => arr.sort(() => Math.random() - 0.5);

// Fisher-Yates: 모든 순열이 동일한 확률 (1/n!)
const correct = () => fisherYatesShuffle(arr);

// 3개 원소 [1,2,3]의 가능한 순열: 6가지 (3!)
// 잘못된 방법: 각 순열이 16.67%가 아닌 불균등한 확률
// Fisher-Yates: 각 순열이 정확히 16.67% (1/6)

// 1,000,000개 원소도 단 한 번의 순회로 완료!
const huge = Array.from({length: 1000000}, (_, i) => i);
fisherYatesShuffle(huge);  // ~1ms

// ❌ 절대 이렇게 하지 마세요!
const arr = [1, 2, 3, 4, 5];
arr.sort(() => Math.random() - 0.5);

// 문제점:
// 1. 편향 발생 - 특정 순열이 다른 것보다 더 자주 나옴
// 2. 불안정 - 브라우저마다 다른 결과
// 3. 느림 - O(n log n)

// [1, 2, 3]을 10,000번 섞었을 때
const results = {
  '[1,2,3]': 1650,  // 16.5% (이상적: 16.67%)
  '[1,3,2]': 1823,  // 18.2% ❌ 편향!
  '[2,1,3]': 1542,  // 15.4% ❌ 편향!
  '[2,3,1]': 1789,  // 17.9%
  '[3,1,2]': 1612,  // 16.1%
  '[3,2,1]': 1584   // 15.8% ❌ 편향!
};

// ❌ 잘못된 구현
for (let i = 0; i < n; i++) {
  const j = Math.floor(Math.random() * n);  // 항상 전체 범위!
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

// 문제: 매번 전체 배열에서 선택 → 편향 발생
// 올바른 방법: i부터 끝까지만 선택

const arr = [1, 2, 3, 4, 5];

// 초기 상태
[1, 2, 3, 4, 5]
              ↑ i=4

// i=4: [0..4] 중 무작위 선택 (예: j=1)
[1, 2, 3, 4, 5]
    ↑        ↑
   j=1      i=4
// 교환 후: [1, 5, 3, 4, 2] (인덱스 1과 4 교환)

// i=3: [0..3] 중 무작위 선택 (예: j=3)
[1, 5, 3, 4 | 2]
         ↑
        j=i=3
// 교환 후: [1, 5, 3, 4 | 2] (자기 자신과 교환 = 변화 없음)

// i=2: [0..2] 중 무작위 선택 (예: j=0)
[1, 5, 3 | 4, 2]
 ↑     ↑
j=0   i=2
// 교환 후: [3, 5, 1 | 4, 2]

// i=1: [0..1] 중 무작위 선택 (예: j=1)
[3, 5 | 1, 4, 2]
    ↑
   j=i=1
// 교환 후: [3, 5 | 1, 4, 2]

// i=0: [0..0] 중 무작위 선택 (j=0만 가능)
[3 | 5, 1, 4, 2]
 ↑
i=j=0
// 최종: [3, 5, 1, 4, 2] ✅

/**
 * Fisher-Yates shuffle (현대판, Durstenfeld 버전)
 * @param {Array} arr - 섞을 배열
 * @returns {Array} - 섞인 배열 (원본 변경)
 */
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 deck = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(fisherYatesShuffle(deck));
// [3, 7, 1, 9, 5, 10, 2, 4, 8, 6] (무작위)

/**
 * 암호학적으로 안전한 Fisher-Yates shuffle
 * (예측 불가능한 난수 생성)
 */
function cryptoShuffle(arr) {
  const result = [...arr];

  for (let i = result.length - 1; i > 0; i--) {
    // crypto.getRandomValues()를 사용한 안전한 난수
    const randomBuffer = new Uint32Array(1);
    crypto.getRandomValues(randomBuffer);
    const j = randomBuffer[0] % (i + 1);

    [result[i], result[j]] = [result[j], result[i]];
  }

  return result;
}

// 보안이 중요한 경우 사용
const sensitiveData = ['password1', 'password2', 'password3'];
cryptoShuffle(sensitiveData);

function fisherYatesDebug(arr) {
  console.log('초기 배열:', [...arr]);
  const result = [...arr];

  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));

    console.log(`\n단계 ${result.length - i}:`);
    console.log(`  i=${i}, j=${j}`);
    console.log(`  교환 전: [${result}]`);
    console.log(`  교환: arr[${i}](${result[i]}) ↔ arr[${j}](${result[j]})`);

    [result[i], result[j]] = [result[j], result[i]];

    console.log(`  교환 후: [${result}]`);
    console.log(`  확정: [${result.slice(i).join(', ')}]`);
  }

  console.log('\n최종 결과:', result);
  return result;
}

// 실행
fisherYatesDebug([1, 2, 3, 4, 5]);

for (let i = arr.length - 1; i > 0; i--) {  // n-1번 반복
  const j = Math.floor(Math.random() * (i + 1));  // O(1)
  [arr[i], arr[j]] = [arr[j], arr[i]];  // O(1)
}

// 총 시간: (n-1) × O(1) = O(n)

function benchmark(size) {
  const arr = Array.from({length: size}, (_, i) => i);

  console.time(`Fisher-Yates (${size}개)`);
  fisherYatesShuffle(arr);
  console.timeEnd(`Fisher-Yates (${size}개)`);
}

benchmark(1000);      // ~0.01ms
benchmark(10000);     // ~0.1ms
benchmark(100000);    // ~1ms
benchmark(1000000);   // ~10ms

// 카드 덱 생성 및 섞기
function createDeck() {
  const suits = ['♠', '♥', '♦', '♣'];
  const ranks = ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K'];

  const deck = [];
  for (const suit of suits) {
    for (const rank of ranks) {
      deck.push({suit, rank});
    }
  }

  return fisherYatesShuffle(deck);
}

const deck = createDeck();
console.log(deck[0]);  // {suit: '♦', rank: '7'} (무작위)

// 카드 나누기
function dealCards(deck, players, cardsPerPlayer) {
  const hands = Array.from({length: players}, () => []);

  for (let i = 0; i < cardsPerPlayer; i++) {
    for (let p = 0; p < players; p++) {
      hands[p].push(deck.pop());
    }
  }

  return hands;
}

const hands = dealCards(deck, 4, 5);  // 4명에게 5장씩

class MusicPlayer {
  constructor(songs) {
    this.originalOrder = songs;
    this.shuffled = null;
    this.currentIndex = 0;
  }

  shuffle() {
    this.shuffled = fisherYatesShuffle([...this.originalOrder]);
    this.currentIndex = 0;
    return this.shuffled[0];
  }

  next() {
    if (!this.shuffled) {
      throw new Error('Please shuffle first');
    }

    this.currentIndex++;
    if (this.currentIndex >= this.shuffled.length) {
      // 끝에 도달하면 다시 섞기
      this.shuffle();
    }

    return this.shuffled[this.currentIndex];
  }

  unshuffle() {
    this.shuffled = null;
    this.currentIndex = 0;
  }
}

// 사용
const player = new MusicPlayer([
  'Song A', 'Song B', 'Song C', 'Song D', 'Song E'
]);

player.shuffle();  // 'Song C' (무작위)
player.next();     // 'Song A' (무작위)
player.next();     // 'Song E' (무작위)

function assignABTest(users, variants) {
  // 사용자 ID를 섞어서 무작위 배정
  const shuffled = fisherYatesShuffle([...users]);
  const groupSize = Math.ceil(shuffled.length / variants.length);

  const assignments = {};

  shuffled.forEach((user, index) => {
    const variantIndex = Math.floor(index / groupSize);
    const variant = variants[Math.min(variantIndex, variants.length - 1)];
    assignments[user.id] = variant;
  });

  return assignments;
}

// 사용
const users = [
  {id: 1, name: 'Alice'},
  {id: 2, name: 'Bob'},
  {id: 3, name: 'Charlie'},
  {id: 4, name: 'David'}
];

const assignments = assignABTest(users, ['A', 'B']);
// {1: 'B', 2: 'A', 3: 'A', 4: 'B'} (무작위)

/**
 * 배열에서 n개의 무작위 샘플 추출
 */
function randomSample(arr, n) {
  if (n > arr.length) {
    throw new Error('Sample size cannot exceed array length');
  }

  const shuffled = fisherYatesShuffle([...arr]);
  return shuffled.slice(0, n);
}

// 데이터 과학: 훈련/테스트 분할
const dataset = Array.from({length: 1000}, (_, i) => ({
  id: i,
  data: Math.random()
}));

const trainSize = Math.floor(dataset.length * 0.8);  // 80%
const shuffled = fisherYatesShuffle([...dataset]);

const trainSet = shuffled.slice(0, trainSize);
const testSet = shuffled.slice(trainSize);

console.log(`Train: ${trainSet.length}, Test: ${testSet.length}`);
// Train: 800, Test: 200

// ❌ 잘못된 구현 1: 항상 전체 범위
for (let i = 0; i < n; i++) {
  const j = Math.floor(Math.random() * n);  // 항상 0~n-1
  [arr[i], arr[j]] = [arr[j], arr[i]];
}
// 문제: 이미 섞인 부분도 다시 섞음 → 편향

// ❌ 잘못된 구현 2: 범위 하나 작음
for (let i = arr.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * i);  // 0~i-1 (i 제외!)
  [arr[i], arr[j]] = [arr[j], arr[i]];
}
// 문제: 자기 자신과 교환 불가 → 편향

// ✅ 올바른 구현
for (let i = arr.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));  // 0~i (i 포함)
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

// ❌ 가장 흔한 실수!
arr.sort(() => Math.random() - 0.5);

// 문제점:
// 1. 비교 함수가 일관성이 없음
// 2. 정렬 알고리즘의 가정 위반
// 3. 브라우저마다 다른 결과
// 4. 편향 발생 (특정 순열이 과대/과소 표현)

// ❌ 원본이 변경됨
const original = [1, 2, 3, 4, 5];
fisherYatesShuffle(original);
console.log(original);  // [3, 1, 5, 2, 4] - 변경됨!

// ✅ 원본 보호
function shuffleImmutable(arr) {
  const copy = [...arr];
  return fisherYatesShuffle(copy);
}

const original = [1, 2, 3, 4, 5];
const shuffled = shuffleImmutable(original);
console.log(original);  // [1, 2, 3, 4, 5] - 안전!

// Math.random()의 한계
// - 예측 가능 (보안 용도 부적합)
// - 긴 배열에서 모든 순열 불가능

// n=52 (카드 덱)일 때:
// - 가능한 순열: 52! ≈ 8×10^67
// - Math.random()의 주기: 2^53 ≈ 9×10^15

// 실제로는 극히 일부 순열만 생성 가능!

// ✅ 보안이 중요하면 crypto.getRandomValues() 사용
function cryptoShuffle(arr) {
  const result = [...arr];
  for (let i = result.length - 1; i > 0; i--) {
    const randomBuffer = new Uint32Array(1);
    crypto.getRandomValues(randomBuffer);
    const j = randomBuffer[0] % (i + 1);
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

/**
 * Sattolo's Algorithm
 * 모든 원소가 원래 위치에서 이동하는 순열만 생성
 */
function sattoloShuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    // 차이점: i를 제외 (0부터 i-1까지만)
    const j = Math.floor(Math.random() * i);  // i+1이 아닌 i
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

// 차이점
const original = [1, 2, 3, 4, 5];

// Fisher-Yates: [1, 2, 3, 4, 5]도 가능 (원본과 같을 수 있음)
// Sattolo: [1, 2, 3, 4, 5]는 불가능 (모두 이동해야 함)

/**
 * Fisher-Yates의 무작위성 검증
 */
function testRandomness(shuffleFunc, iterations = 100000) {
  const arr = [1, 2, 3];
  const permutations = {};

  for (let i = 0; i < iterations; i++) {
    const shuffled = shuffleFunc([...arr]);
    const key = shuffled.join(',');
    permutations[key] = (permutations[key] || 0) + 1;
  }

  console.log('순열 분포:');
  const expected = iterations / 6;  // 3! = 6

  for (const [perm, count] of Object.entries(permutations)) {
    const percentage = (count / iterations * 100).toFixed(2);
    const deviation = ((count - expected) / expected * 100).toFixed(2);
    console.log(`[${perm}]: ${count}회 (${percentage}%, 편차: ${deviation}%)`);
  }
}

// Fisher-Yates 테스트
console.log('=== Fisher-Yates ===');
testRandomness(fisherYatesShuffle);

// 잘못된 방법 테스트
console.log('\n=== sort() + random ===');
testRandomness(arr => arr.sort(() => Math.random() - 0.5));

// Fisher-Yates shuffle을 직접 구현해보세요
function fisherYatesShuffle(arr) {
  // 여기에 코드 작성
}

const test = [1, 2, 3, 4, 5];
console.log(fisherYatesShuffle(test));
// [3, 5, 1, 4, 2] (무작위)

// 배열의 앞 n개만 섞기
function partialShuffle(arr, n) {
  // 힌트: Fisher-Yates를 n번만 반복
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(partialShuffle(arr, 3));
// [7, 2, 9, 4, 5, 6, 1, 8, 3, 10] - 앞 3개만 랜덤

// 가중치에 따라 특정 원소가 앞에 올 확률 높이기
function weightedShuffle(arr, weights) {
  // 도전 과제!
}

const items = ['A', 'B', 'C', 'D'];
const weights = [10, 5, 3, 1];  // A가 앞에 올 확률 높음

// 이 10줄이면 완벽한 셔플!
function fisherYatesShuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}