隨機演算法完全指南 — QuickSelect、Reservoir Sampling 與 Fisher-Yates 洗牌 | 資料結構與演算法

// ─── Randomized QuickSort — Las Vegas 演算法 ─────────────────

function randomizedQuickSort(arr: number[], lo: number = 0, hi: number = arr.length - 1): void {
  if (lo >= hi) return;

  // 隨機選 pivot，避免對抗性最壞情況
  const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]]; // 將 pivot 移到末尾

  // Lomuto Partition
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  const p = i + 1;

  randomizedQuickSort(arr, lo, p - 1);
  randomizedQuickSort(arr, p + 1, hi);
}

// 測試
const data = [5, 3, 8, 1, 9, 2, 7, 4, 6];
randomizedQuickSort(data);
console.log(data); // 輸出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

// 對抗性測試：已排序輸入不會退化
const sorted = Array.from({ length: 10000 }, (_, i) => i);
randomizedQuickSort(sorted); // 期望 O(n log n)，不會退化到 O(n²)

// ─── QuickSelect — 期望 O(n) 找第 k 小元素 ─────────────────

function quickSelect(arr: number[], k: number): number {
  // k 為 1-indexed（第 k 小）
  return _quickSelect(arr, 0, arr.length - 1, k - 1);
}

function _quickSelect(arr: number[], lo: number, hi: number, k: number): number {
  if (lo === hi) return arr[lo];

  // 隨機選 pivot
  const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]];

  // Lomuto Partition
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  const p = i + 1;

  if (k === p) {
    return arr[p];
  } else if (k < p) {
    return _quickSelect(arr, lo, p - 1, k);   // 只遞迴左半
  } else {
    return _quickSelect(arr, p + 1, hi, k);   // 只遞迴右半
  }
}

// 測試
console.log(quickSelect([7, 2, 5, 1, 8, 3], 3)); // 輸出：3（第 3 小的元素）
console.log(quickSelect([7, 2, 5, 1, 8, 3], 1)); // 輸出：1（最小元素）
console.log(quickSelect([7, 2, 5, 1, 8, 3], 6)); // 輸出：8（最大元素）

// ─── Reservoir Sampling — 串流等機率抽樣 ─────────────────────

class ReservoirSampler<T> {
  private reservoir: T[];
  private count: number = 0;
  private k: number;

  constructor(k: number) {
    this.k = k;
    this.reservoir = [];
  }

  // 處理串流中的每個元素（O(1) per element）
  add(item: T): void {
    this.count++;

    if (this.reservoir.length < this.k) {
      // 前 k 個元素直接放入水庫
      this.reservoir.push(item);
    } else {
      // 以 k/count 機率替換水庫中的某個元素
      const j = Math.floor(Math.random() * this.count);
      if (j < this.k) {
        this.reservoir[j] = item;
      }
    }
  }

  getSample(): T[] {
    return [...this.reservoir];
  }
}

// 測試：從 1~1000 中隨機取 5 個
const sampler = new ReservoirSampler<number>(5);
for (let i = 1; i <= 1000; i++) {
  sampler.add(i);
}
console.log(sampler.getSample()); // 從 1~1000 中隨機取 5 個，每個被選機率 = 5/1000

// ─── Reservoir Sampling k=1：鏈結串列隨機節點 ────────────────

class ListNode {
  val: number;
  next: ListNode | null = null;
  constructor(val: number) { this.val = val; }
}

class Solution382 {
  private head: ListNode | null;

  constructor(head: ListNode | null) {
    this.head = head;
  }

  getRandom(): number {
    let result = this.head!.val;
    let count = 1;
    let curr = this.head!.next;

    while (curr) {
      count++;
      // 以 1/count 機率用當前節點替換結果
      if (Math.floor(Math.random() * count) === 0) {
        result = curr.val;
      }
      curr = curr.next;
    }
    return result;
  }
}

// 驗證均勻性
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

const sol = new Solution382(head);
const freq: Record<number, number> = { 1: 0, 2: 0, 3: 0 };
const trials = 30000;

for (let i = 0; i < trials; i++) {
  freq[sol.getRandom()]++;
}
Object.entries(freq).forEach(([val, cnt]) => {
  console.log(`節點${val}：${(cnt / trials * 100).toFixed(1)}%（期望 33.3%）`);
});
// 輸出：每個節點約 33.3%（±1% 隨機誤差）

// ─── Fisher-Yates Shuffle — 正確的均勻洗牌 ──────────────────

function fisherYatesShuffle<T>(arr: T[]): T[] {
  const result = [...arr]; // 不修改原陣列
  const n = result.length;

  // 從後向前遍歷，每步從 [0, i] 中隨機選一個位置與 i 交換
  for (let i = n - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

// 測試
console.log(fisherYatesShuffle([1, 2, 3, 4, 5]));
// 輸出：[1, 2, 3, 4, 5] 的某個隨機排列

// ─── 錯誤示範：Naive Shuffle（不均勻！）────────────────────

function naiveShuffle<T>(arr: T[]): T[] {
  const result = [...arr];
  const n = result.length;

  // 錯誤：每步都從 [0, n-1] 中隨機選
  for (let i = 0; i < n; i++) {
    const j = Math.floor(Math.random() * n); // 應該是 rand(0, i) 而非 rand(0, n-1)
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

// 驗證不均勻性
function compareShuffles(): void {
  const n = 3;
  const trials = 600000;
  const fisherCounts = new Map<string, number>();
  const naiveCounts = new Map<string, number>();

  for (let t = 0; t < trials; t++) {
    const arr1 = [1, 2, 3];
    const arr2 = [1, 2, 3];

    const s1 = fisherYatesShuffle(arr1).join(',');
    const s2 = naiveShuffle(arr2).join(',');

    fisherCounts.set(s1, (fisherCounts.get(s1) ?? 0) + 1);
    naiveCounts.set(s2, (naiveCounts.get(s2) ?? 0) + 1);
  }

  console.log('Fisher-Yates（期望每種 100000 次）：');
  for (const [perm, cnt] of [...fisherCounts].sort()) {
    console.log(`  ${perm}: ${cnt}`);
  }

  console.log('Naive Shuffle（分布不均勻）：');
  for (const [perm, cnt] of [...naiveCounts].sort()) {
    console.log(`  ${perm}: ${cnt}`);
  }
}
// Fisher-Yates：6 種排列各約 100000 次
// Naive Shuffle：某些排列出現次數明顯偏多或偏少

// ─── LeetCode 384：設計可重置洗牌的資料結構 ─────────────────

class ShuffleArray {
  private original: number[];
  private current: number[];

  constructor(nums: number[]) {
    this.original = [...nums];
    this.current = [...nums];
  }

  reset(): number[] {
    this.current = [...this.original];
    return this.current;
  }

  shuffle(): number[] {
    const n = this.current.length;
    for (let i = n - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [this.current[i], this.current[j]] = [this.current[j], this.current[i]];
    }
    return this.current;
  }
}

// 測試
const sa = new ShuffleArray([1, 2, 3]);
console.log(sa.shuffle()); // 輸出：某個隨機排列
console.log(sa.reset());   // 輸出：[1, 2, 3]
console.log(sa.shuffle()); // 輸出：另一個隨機排列

// ─── Skip List — 隨機化有序字典 ─────────────────────────────

const MAX_LEVEL = 16;
const PROBABILITY = 0.5;

class SkipListNode {
  val: number;
  forward: (SkipListNode | null)[];

  constructor(val: number, level: number) {
    this.val = val;
    this.forward = new Array(level).fill(null);
  }
}

class SkipList {
  private head: SkipListNode;
  private level: number = 1;
  private size: number = 0;

  constructor() {
    this.head = new SkipListNode(-Infinity, MAX_LEVEL);
  }

  // 隨機生成層數（幾何分佈）
  private randomLevel(): number {
    let lvl = 1;
    while (Math.random() < PROBABILITY && lvl < MAX_LEVEL) lvl++;
    return lvl;
  }

  // 搜索：O(log n) 期望
  search(target: number): boolean {
    let curr = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (curr.forward[i] && curr.forward[i]!.val < target) {
        curr = curr.forward[i]!;
      }
    }
    curr = curr.forward[0]!;
    return curr !== null && curr.val === target;
  }

  // 插入：O(log n) 期望
  insert(val: number): void {
    const update: (SkipListNode | null)[] = new Array(MAX_LEVEL).fill(null);
    let curr = this.head;

    for (let i = this.level - 1; i >= 0; i--) {
      while (curr.forward[i] && curr.forward[i]!.val < val) {
        curr = curr.forward[i]!;
      }
      update[i] = curr;
    }

    const newLevel = this.randomLevel();
    if (newLevel > this.level) {
      for (let i = this.level; i < newLevel; i++) update[i] = this.head;
      this.level = newLevel;
    }

    const newNode = new SkipListNode(val, newLevel);
    for (let i = 0; i < newLevel; i++) {
      newNode.forward[i] = update[i]!.forward[i];
      update[i]!.forward[i] = newNode;
    }
    this.size++;
  }

  // 刪除：O(log n) 期望
  erase(val: number): boolean {
    const update: (SkipListNode | null)[] = new Array(MAX_LEVEL).fill(null);
    let curr = this.head;

    for (let i = this.level - 1; i >= 0; i--) {
      while (curr.forward[i] && curr.forward[i]!.val < val) {
        curr = curr.forward[i]!;
      }
      update[i] = curr;
    }

    const target = curr.forward[0];
    if (!target || target.val !== val) return false;

    for (let i = 0; i < this.level; i++) {
      if (update[i]!.forward[i] !== target) break;
      update[i]!.forward[i] = target.forward[i];
    }

    while (this.level > 1 && !this.head.forward[this.level - 1]) {
      this.level--;
    }
    this.size--;
    return true;
  }
}

// 測試
const sl = new SkipList();
[3, 6, 7, 9, 12, 17, 19, 21, 25].forEach(v => sl.insert(v));
console.log(sl.search(7));  // 輸出：true
console.log(sl.search(8));  // 輸出：false
sl.erase(7);
console.log(sl.search(7));  // 輸出：false

// ─── Miller-Rabin 素數測試 — Monte Carlo 演算法 ──────────────

function millerRabin(n: number, k: number = 10): boolean {
  // 處理邊界情況
  if (n < 2) return false;
  if (n === 2 || n === 3) return true;
  if (n % 2 === 0) return false;

  // 將 n-1 寫成 2^r × d 的形式
  let r = 0;
  let d = n - 1;
  while (d % 2 === 0) {
    r++;
    d = Math.floor(d / 2);
  }

  // 進行 k 輪測試
  for (let i = 0; i < k; i++) {
    // 隨機選取 a ∈ [2, n-2]
    const a = 2 + Math.floor(Math.random() * (n - 3));

    let x = modPow(a, d, n); // a^d mod n

    if (x === 1 || x === n - 1) continue;

    let composite = true;
    for (let j = 0; j < r - 1; j++) {
      x = modPow(x, 2, n); // x = x² mod n
      if (x === n - 1) {
        composite = false;
        break;
      }
    }

    if (composite) return false; // 確定是合數
  }

  return true; // 可能是素數（誤判率 ≤ 4^-k）
}

// 快速冪取模
function modPow(base: number, exp: number, mod: number): number {
  let result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) {
      result = (result * base) % mod;
    }
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}

// 測試
console.log(millerRabin(97));    // 輸出：true（97 是素數）
console.log(millerRabin(100));   // 輸出：false（100 不是素數）
console.log(millerRabin(7919));  // 輸出：true（7919 是素數）
console.log(millerRabin(561));   // 輸出：false（561 是 Carmichael 數）
// k=10 時，將合數誤判為素數的機率 ≤ 4^-10 ≈ 0.000001

#include <vector>
#include <random>
#include <algorithm>
#include <iostream>
using namespace std;

mt19937 rng(random_device{}());

// ─── Randomized QuickSort ───────────────────────────────────

int partition(vector<int>& arr, int lo, int hi) {
    // 隨機選 pivot
    int pivotIdx = lo + rng() % (hi - lo + 1);
    swap(arr[pivotIdx], arr[hi]);

    int pivot = arr[hi], i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);
    }
    swap(arr[i + 1], arr[hi]);
    return i + 1;
}

void randomizedQuickSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);
    randomizedQuickSort(arr, lo, p - 1);
    randomizedQuickSort(arr, p + 1, hi);
}

// ─── QuickSelect ────────────────────────────────────────────

int quickSelect(vector<int>& arr, int lo, int hi, int k) {
    if (lo == hi) return arr[lo];

    int p = partition(arr, lo, hi);
    if (k == p) return arr[p];
    else if (k < p) return quickSelect(arr, lo, p - 1, k);
    else return quickSelect(arr, p + 1, hi, k);
}

int main() {
    vector<int> data = {5, 3, 8, 1, 9, 2, 7, 4, 6};
    randomizedQuickSort(data, 0, data.size() - 1);
    for (int x : data) cout << x << " ";
    // 輸出：1 2 3 4 5 6 7 8 9
    cout << endl;

    vector<int> arr = {7, 2, 5, 1, 8, 3};
    cout << quickSelect(arr, 0, arr.size() - 1, 2) << endl;
    // 輸出：3（第 3 小，0-indexed 為 2）
    return 0;
}

#include <vector>
#include <random>
#include <iostream>
using namespace std;

// ─── Reservoir Sampling ─────────────────────────────────────

template<typename T>
class ReservoirSampler {
    vector<T> reservoir;
    int count = 0;
    int k;
    mt19937 rng{random_device{}()};

public:
    ReservoirSampler(int k) : k(k) {}

    void add(const T& item) {
        count++;
        if ((int)reservoir.size() < k) {
            reservoir.push_back(item);
        } else {
            uniform_int_distribution<int> dist(0, count - 1);
            int j = dist(rng);
            if (j < k) reservoir[j] = item;
        }
    }

    vector<T> getSample() const { return reservoir; }
};

// ─── Fisher-Yates Shuffle ───────────────────────────────────

void fisherYatesShuffle(vector<int>& arr) {
    int n = arr.size();
    mt19937 rng(random_device{}());

    for (int i = n - 1; i > 0; i--) {
        uniform_int_distribution<int> dist(0, i);
        int j = dist(rng);
        swap(arr[i], arr[j]);
    }
}

// C++ STL 提供的 std::shuffle 底層即 Fisher-Yates
void stdShuffle(vector<int>& arr) {
    mt19937 rng(random_device{}());
    shuffle(arr.begin(), arr.end(), rng);
}

int main() {
    // Reservoir Sampling 測試
    ReservoirSampler<int> sampler(3);
    for (int i = 1; i <= 1000; i++) sampler.add(i);
    auto sample = sampler.getSample();
    for (int x : sample) cout << x << " ";
    cout << endl;
    // 輸出：從 1~1000 中隨機取 3 個

    // Fisher-Yates Shuffle 測試
    vector<int> arr = {1, 2, 3, 4, 5};
    fisherYatesShuffle(arr);
    for (int x : arr) cout << x << " ";
    cout << endl;
    // 輸出：某個隨機排列
    return 0;
}

#include <vector>
#include <random>
#include <climits>
#include <iostream>
using namespace std;

struct SkipNode {
    int val;
    vector<SkipNode*> forward;
    SkipNode(int v, int lvl) : val(v), forward(lvl, nullptr) {}
};

class SkipList {
    static const int MAX_LEVEL = 16;
    static constexpr double P = 0.5;

    SkipNode* head;
    int level = 1;
    mt19937 rng{random_device{}()};

    int randomLevel() {
        int lvl = 1;
        uniform_real_distribution<double> dist(0, 1);
        while (dist(rng) < P && lvl < MAX_LEVEL) lvl++;
        return lvl;
    }

public:
    SkipList() : head(new SkipNode(INT_MIN, MAX_LEVEL)) {}

    bool search(int target) {
        SkipNode* curr = head;
        for (int i = level - 1; i >= 0; i--)
            while (curr->forward[i] && curr->forward[i]->val < target)
                curr = curr->forward[i];
        curr = curr->forward[0];
        return curr && curr->val == target;
    }

    void insert(int val) {
        vector<SkipNode*> update(MAX_LEVEL, nullptr);
        SkipNode* curr = head;
        for (int i = level - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < val)
                curr = curr->forward[i];
            update[i] = curr;
        }
        int newLvl = randomLevel();
        if (newLvl > level) {
            for (int i = level; i < newLvl; i++) update[i] = head;
            level = newLvl;
        }
        SkipNode* node = new SkipNode(val, newLvl);
        for (int i = 0; i < newLvl; i++) {
            node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = node;
        }
    }

    bool erase(int val) {
        vector<SkipNode*> update(MAX_LEVEL, nullptr);
        SkipNode* curr = head;
        for (int i = level - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < val)
                curr = curr->forward[i];
            update[i] = curr;
        }
        SkipNode* target = curr->forward[0];
        if (!target || target->val != val) return false;
        for (int i = 0; i < level; i++) {
            if (update[i]->forward[i] != target) break;
            update[i]->forward[i] = target->forward[i];
        }
        while (level > 1 && !head->forward[level - 1]) level--;
        delete target;
        return true;
    }

    ~SkipList() {
        SkipNode* curr = head;
        while (curr) {
            SkipNode* next = curr->forward[0];
            delete curr;
            curr = next;
        }
    }
};

int main() {
    SkipList sl;
    for (int v : {3, 6, 7, 9, 12, 17, 19, 21, 25}) sl.insert(v);
    cout << boolalpha;
    cout << sl.search(7) << endl;   // 輸出：true
    cout << sl.search(8) << endl;   // 輸出：false
    sl.erase(7);
    cout << sl.search(7) << endl;   // 輸出：false
    return 0;
}

// ─── Weighted Reservoir Sampling（Efraimidis-Spirakis 算法）───

class WeightedReservoirSampler<T> {
  private reservoir: { item: T; key: number }[];
  private k: number;

  constructor(k: number) {
    this.k = k;
    this.reservoir = [];
  }

  add(item: T, weight: number): void {
    // 計算隨機鍵：key = random^(1/weight)
    const key = Math.pow(Math.random(), 1 / weight);

    if (this.reservoir.length < this.k) {
      this.reservoir.push({ item, key });
      if (this.reservoir.length === this.k) {
        // 建立最小堆（以 key 排序）
        this.reservoir.sort((a, b) => a.key - b.key);
      }
    } else if (key > this.reservoir[0].key) {
      // 替換最小 key 的元素
      this.reservoir[0] = { item, key };
      this.reservoir.sort((a, b) => a.key - b.key);
    }
  }

  getSample(): T[] {
    return this.reservoir.map(r => r.item);
  }
}

// ─── Treap 基本概念 ─────────────────────────────────────────

// Treap = Tree + Heap
// 每個節點有兩個值：
//   - key：遵守 BST 性質（左小右大）
//   - priority：隨機值，遵守 Max-Heap 性質（父大於子）
// 兩個性質聯合保證樹的期望高度為 O(log n)

// 插入時：先按 BST 規則插入，再按 priority 旋轉上浮
// 刪除時：將節點旋轉到葉子再刪除

// ─── LeetCode 398：Reservoir Sampling 變體 ──────────────────

class Solution398 {
  private nums: number[];

  constructor(nums: number[]) {
    this.nums = nums;
  }

  pick(target: number): number {
    let result = -1;
    let count = 0;
    for (let i = 0; i < this.nums.length; i++) {
      if (this.nums[i] === target) {
        count++;
        if (Math.floor(Math.random() * count) === 0) {
          result = i;
        }
      }
    }
    return result;
  }
}

// 時間：O(n) per pick，空間：O(1)
// 比預先建 HashMap 省空間，適用於記憶體受限場景

// ─── LeetCode 528：前綴和 + 二分搜索 ────────────────────────

class WeightedRandom {
  private prefixSum: number[];
  private total: number;

  constructor(w: number[]) {
    this.prefixSum = [];
    let sum = 0;
    for (const weight of w) {
      sum += weight;
      this.prefixSum.push(sum);
    }
    this.total = sum;
  }

  pickIndex(): number {
    const target = Math.floor(Math.random() * this.total) + 1;
    let lo = 0, hi = this.prefixSum.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.prefixSum[mid] < target) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
}

// 直覺圖解：
// w = [1, 3, 2]，total = 6，prefixSum = [1, 4, 6]
// 數軸：[1] [2,3,4] [5,6]
//        ↑    ↑       ↑
//      索引0  索引1    索引2
// 隨機選 1~6，二分找第一個 prefixSum[i] >= target

// 時間：建構 O(n)，查詢 O(log n)
// 空間：O(n)

// ─── LeetCode 215：QuickSelect 找第 k 大 ────────────────────

function findKthLargest(nums: number[], k: number): number {
  // 第 k 大 = 第 (n - k + 1) 小 → 0-indexed 為 n - k
  const target = nums.length - k;
  return _select(nums, 0, nums.length - 1, target);
}

function _select(arr: number[], lo: number, hi: number, k: number): number {
  if (lo === hi) return arr[lo];

  const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]];

  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  const p = i + 1;

  if (k === p) return arr[p];
  else if (k < p) return _select(arr, lo, p - 1, k);
  else return _select(arr, p + 1, hi, k);
}

// 測試
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 輸出：5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 輸出：4
// 期望時間：O(n)，空間：O(1)