# DCL 演算法規格書

**方向約束鎖定（Directional Constraint Locking）**
版本 0.7 — 2026-06-24

---

## 1. 概述

方向約束鎖定（DCL）是一種以空間移動驅動的多維篩選演算法。使用者在二維畫布上沿 8 個方向導航；每個方向對應一個資料維度。往某方向移動會鎖定該維度的值，鎖定的約束持續累積，逐步縮小候選池。

透過 FIFO 解鎖機制，演算法保證導航永遠不會陷入死路。

---

## 2. 形式化定義

### 2.1 符號表

| 符號 | 定義 |
|------|------|
| C | 所有卡片的集合，\|C\| = n |
| D | {↖, ↑, ↗, ←, →, ↙, ↓, ↘}，共 8 個方向 |
| N | 值域大小（可設定，預設 8，需 N ≥ 8） |
| A(c, d) | 屬性函數：卡片 c 在方向 d 上的值。A : C × D → {1…N} |
| L | 當前鎖定集合，L ⊆ D × {1…N} |
| Q | 鎖定順序佇列（FIFO），記錄方向被鎖定的先後順序 |
| c_t | 時刻 t 的當前卡片 |

### 2.2 排列約束

對所有卡片 c ∈ C，函數 A(c, ·) : D → {1…N} 從 N 個可能值中為 8 個方向各選取**不重複**的整數（N ≥ 8，預設 N = 8）。

- 當 N = 8 時，A(c, ·) 為**雙射（完整排列）**，值集恰為 {1, 2, 3, 4, 5, 6, 7, 8}。
- 當 N > 8 時，每張卡片從 {1…N} 中挑選 8 個相異的值，即 C(N, 8) × 8! 種可能的賦值方式之一。

**意涵**：同一張卡片不可能在兩個方向持有相同的值。這確保了鎖定約束時的最大區分度。

### 2.3 候選池

```
P(L, c_t) = { c ∈ C | c ≠ c_t ∧ ∀(d, v) ∈ L : A(c, d) = v }
```

候選池是所有滿足每個鎖定約束的卡片集合（排除當前卡片）。

### 2.4 導航函數：nav(d)

給定方向 d，導航步驟如下：

```
1. 鎖定 — 若 d 尚未被鎖定：
     L ← L ∪ {(d, A(c_t, d))}
     Q.enqueue(d)

2. 查詢 — 計算候選池：
     P ← P(L, c_t)

3. FIFO 解鎖 — 若 P = ∅，釋放最早的鎖定直到有候選：
     while P = ∅ 且 Q ≠ ∅：
       d' ← Q.dequeue()        // 最早鎖定的方向
       L  ← L \ {(d', ·)}      // 移除該約束
       P  ← P(L, c_t)          // 重新計算

4. 隨機選取 — 從池中隨機挑選一張卡片：
     c_t ← P[random(0, |P|-1)]
```

**已鎖定方向的行為**：當 d ∈ L（方向已鎖定），步驟 1 被跳過 — 不新增約束。函數直接以現有鎖定集進入步驟 2，效果等同於在同一候選池中再次隨機挑選。

**非確定性**：每次導航從候選池中隨機選取，相同操作序列不保證產生相同結果。這增強了探索的驚喜感，但犧牲了可重現性。Undo/redo 透過快照機制仍能精確回溯。

---

## 3. 性質

### 3.1 單調累積

在導航過程中 |L| 單調不遞減，除非 FIFO 解鎖觸發。每次 `nav(d)` 呼叫要麼增加一個約束，要麼保持 L 不變。

### 3.2 最大鎖定數

|L| ≤ |D| = 8。最多只能鎖定 8 個不同的方向維度。

### 3.3 無死路保證

**定理**：對任意卡片集合 C（|C| > 1）和任意當前卡片 c_t，導航函數 `nav(d)` 總能產生非空候選池。

**證明概要**：
- 最壞情況下，FIFO 解鎖移除所有約束，得到 L = ∅。
- 當 L = ∅ 時，P(∅, c_t) = C \ {c_t}。
- 因為 |C| > 1，所以 |P(∅, c_t)| ≥ 1。
- 因此步驟 3 的 while 迴圈必定在 P ≠ ∅ 時終止。 ∎

### 3.4 隨機導航

在固定鎖定集 L 下，候選池 P(L, c_t) 是有限的。每次導航從池中隨機選取一張卡片，不保證遍歷所有候選。這種非確定性設計優先考慮探索的驚喜感而非完整覆蓋。

### 3.5 排列唯一性

因為 A(c, ·) 對每張卡片在 8 個方向上賦予相異的值（無論 N 為何），一張卡片在每個方向最多匹配一個值。這避免了約束匹配的歧義，並確保鎖定集 L 的良定義性（每個方向最多出現一次）。

---

## 4. 複雜度分析

### 4.1 時間複雜度

實作使用在初始化時建立的**倒排索引** `Index[d][v]`。候選池計算透過鎖定維度上的集合交集完成，而非線性掃描。

| 操作 | 複雜度 |
|------|--------|
| 鎖定一個方向 | O(1) |
| 計算 P(L, c_t) | O(最小桶大小 · \|L\|)，透過索引交集 |
| FIFO 解鎖（最壞情況） | O(\|L\| · 最小桶 · \|L\|) |
| 單次 nav(d) 呼叫 | 最壞 O(最小桶 · \|L\|²) |

N 個分類、n 張卡片時，平均桶大小為 n/N。N=20, n=10000 時：每次導航掃描約 500 張而非 10000 張。實測 **50K 張卡片下每次導航 0.13ms**。

退路：未使用索引時（如透過公開的 `getPool`/`getAllMatch` API），複雜度為 O(n · |L|)。

### 4.2 空間複雜度

| 組件 | 空間 |
|------|------|
| 卡片儲存 | O(n · \|D\|) = O(8n) = O(n) |
| 倒排索引 | O(n · \|D\|) = O(8n) = O(n) |
| 鎖定狀態 | O(\|D\|) = O(1) |
| 鎖定佇列 | O(\|D\|) = O(1) |
| （無額外狀態） | — |

### 4.3 進一步優化方向

- **位圖交集**：將每個 `Index[d][v]` 表示為位元集。Pool = 所有鎖定位元集的 AND 運算。O(n/64 · |L|)。適用於超過 10 萬張卡片的場景。

---

## 5. 資料結構

### 5.1 卡片節點

```json
{
  "id": "card_001",
  "attrs": {
    "right": 8,
    "left": 3,
    "up": 7,
    "down": 4,
    "rightUp": 6,
    "leftUp": 2,
    "rightDown": 5,
    "leftDown": 1
  }
}
```

`attrs` 物件將 8 個方向各映射到 {1…N} 中的一個唯一整數（N 為值域大小，預設 8；同一卡片的 8 個值互不相同）。

### 5.2 導航狀態

```json
{
  "current": "card_001",
  "lockMap": { "right": 8, "up": 7 },
  "lockOrder": ["right", "up"]
}
```

| 欄位 | 用途 |
|------|------|
| `current` | 當前活動卡片 |
| `lockMap` | 已鎖定的方向→值對應 |
| `lockOrder` | 鎖定順序的 FIFO 佇列 |

---

## 6. 與既有方法的比較

| 方法 | 相似之處 | 不同之處 |
|------|----------|----------|
| Faceted Search | 多條件篩選 | 條件是預設的，非行為驅動 |
| Graph Traversal | 節點間移動 | 無方向維度語意 |
| Constraint Satisfaction | 累積約束求解 | 非空間導航驅動 |
| Latent Space Navigation | 語意空間探索 | 需要 ML 模型，內部不透明 |
| **DCL** | — | 行為即篩選；移動即定義約束；透明可控 |

---

## 7. 設計考量

### 7.1 候選池大小 vs. 約束數量

n 張卡片鎖定 k 個約束時，期望候選池大小隨約束累積而下降。

**前提假設**：卡片屬性由 {1…N} 中均勻隨機抽取的 8 個相異值組成。真實資料可能存在偏態分佈 — 以下分析提供基準值，實際候選池大小應以實測驗證。

因為每張卡片的 8 個值互不相同，方向間**並非獨立** — 知道一個值會約束其餘的可能性。正確模型使用下降階乘（falling factorial）：

```
E[|P|] ≈ n × P(N-k, 8-k) / P(N, 8)

其中 P(x, y) = x × (x-1) × ... × (x-y+1)（下降階乘）

當 N = 8 時（預設），P(N, 8) = 8!，上式化簡為：
E[|P|] ≈ n / P(8, k) = n × (8-k)! / 8!
```

**N = 8（預設）時：**

| k（鎖定數） | P(8, k) | n=40 時 E[\|P\|] | n=100 時 E[\|P\|] |
|-------------|---------|-------------------|---------------------|
| 1 | 8 | 5.0 | 12.5 |
| 2 | 56 | 0.71 | 1.79 |
| 3 | 336 | 0.12 | 0.30 |
| 4 | 1680 | 0.02 | 0.06 |

**N > 8 時**：較大的值域 N 降低了每個值的碰撞機率，候選池在相同鎖定數下更大，FIFO 解鎖觸發頻率降低。

小卡片集（N = 8）下 FIFO 解鎖會頻繁觸發 — 40 張卡片鎖定 2 個約束時，期望候選池已不足 1。實務建議：**n 至少為 56（= P(8,2)）才能在 2 個同時鎖定下有流暢體驗，至少 336 才能支撐 3 個鎖定**。增大 N 可在不增加卡片數的情況下改善候選池大小。

### 7.2 模糊匹配擴展

嚴格等式約束 `A(c, d) = v` 可放寬為容差窗口：

```
P_fuzzy(L, c_t, ε) = { c ∈ C | c ≠ c_t ∧ ∀(d, v) ∈ L : |A(c, d) - v| ≤ ε }
```

ε=1 時，每個鎖定約匹配更多卡片（嚴格匹配機率約 1/N，模糊匹配約 (2ε+1)/N），大幅增加小資料集的候選池大小。值互不相同的約束對底層資料仍然成立 — 模糊匹配只放寬查詢條件，不改變卡片屬性。

**權衡**：模糊匹配以犧牲區分度為代價換取更大的候選池。ε=1 時約束變得不精確 — 使用者可能看到「接近但非精確」的卡片，這是否符合探索意圖取決於應用場景。容差 ε 應依具體應用調校。

### 7.3 數值賦予策略

約束要求從 {1…N} 中為每張卡片的 8 個方向各選取相異的整數（N ≥ 8，預設 N = 8）。策略包括：

- **隨機抽樣（不重複）**：從 {1…N} 中隨機取 8 個相異值，均勻分佈。N = 8 時退化為完整隨機排列。Prototype 中使用。
- **基於嵌入**：將卡片特徵（如透過 CLIP）映射到 8 個維度，再在每個維度內排序以產生離散值。N 可依所需的粒度設定。
- **人工策展**：領域專家為小型高品質資料集手動賦值。

---

## 8. 插件系統

### 8.1 架構

DCL 引擎支援可選的插件機制。核心演算法保持不變；插件透過包裝或新增方法來擴展引擎實例。

```
DCL.register(name, installer)   // 全域註冊插件
DCL.use(engine, name)           // 將插件掛載到特定引擎實例
```

`installer` 函數接收引擎實例，可以：
- 包裝既有方法（如攔截 `navigate` 以加入前後邏輯）
- 新增方法（如 `undo`）
- 透過閉包維護私有狀態

### 8.2 內建插件：`memory`

**用途**：完整狀態的 undo/redo — 沿導航歷史前後移動，每一步都還原**完整的先前狀態**（當前卡片**與**鎖定）。

**狀態**：三個內部堆疊（undo 深度上限 50）：

| 堆疊 | 元素 | 角色 |
|------|------|------|
| `undoStack` | `{ state, dir }` | 每一步先前狀態的完整快照 `{cur, lockMap, lockOrder}` |
| `redoStack` | `{ state, dir }` | 被 `undo()` 彈出的快照，可由 `redo()` 重放 |
| `dirStack` | `dir` | 已走過的方向路徑，用於偵測回退 |

由於每筆元素儲存的是完整快照（而非僅卡片），undo/redo 會還原**整個**導航狀態，包含鎖定集 L 與鎖定順序 Q。這是相對於原本「僅卡片」設計的刻意變更。

**修改的方法**：

| 方法 | 行為 |
|------|------|
| `navigate(d)` | 先計算*方向提示*（見下）。若提示為 `undo`/`redo`，轉交對應方法。否則將當前狀態的完整快照推入 `undoStack`、清空 `redoStack`，再導航 — 並重用 `peek` 快取的目標 id，使先前的 `peek(d)`/`peekAll()` 與實際移動落在**同一張**卡片。 |
| `reset()` | 清空三個堆疊與 peek 快取，再呼叫原始方法。 |

**方向提示**（`dirHint(d)`）：將方向輸入轉譯為 undo/redo，讓空間回退更自然。

- 若 `d` 是上一步方向的**相反**（`OPPOSITE[dirStack.top]`），提示為 `undo`。
- 否則，若 `d` 等於最近一次被撤銷步驟的方向（`redoStack.top.dir`），提示為 `redo`。此判定在**任意**深度皆成立，不限於路徑完全展開時。（`redoStack` 在每次全新 `navigate` 都會清空，故只有在一次或多次 `undo` 之後才非空；且 redo 方向永遠不會等於 `OPPOSITE[dirStack.top]`，因此不會與 undo 情形衝突。）
- 否則為 `null` — 一般的前向導航。

**新增的方法**：

| 方法 | 回傳 | 說明 |
|------|------|------|
| `undo()` | `{card, candidates, allMatches, lockMap, lockOrder, undone:true}` 或 `null` | 彈出 `undoStack`，將當前狀態推入 `redoStack`，並**還原完整快照**（`cur`、`lockMap`、`lockOrder`）。`undoStack` 為空時回傳 `null`。 |
| `redo()` | `{... redone:true}` 或 `null` | 彈出 `redoStack`，將當前狀態推入 `undoStack`，並還原該快照。`redoStack` 為空時回傳 `null`。 |
| `canUndo()` | `boolean` | `undoStack` 是否非空 |
| `canRedo()` | `boolean` | `redoStack` 是否非空 |
| `peek(d)` | `{card, type}` 或 `null` | 預覽方向 d 會到哪張卡片。`type` 為 `'navigate'`、`'undo'` 或 `'redo'`。結果具冪等性：同一狀態下多次呼叫回傳相同結果，且快取的 navigate 目標會被 `navigate(d)` 重用。 |
| `peekAll()` | `{dir: {card, type}}` | 預覽所有 8 個方向。結果被快取，直到下一次改變狀態的呼叫才重算。 |

**undo 的形式化語意**：

```
undo():
  若 undoStack = ∅: 回傳 null
  redoStack.push({ state: snapshot(c_t, L, Q), dir })
  (c_t, L, Q) ← undoStack.pop().state    // 還原完整狀態
  回傳 (c_t, P(L, c_t), L, Q, undone=true)
```

關鍵性質：**undo/redo 還原精確的先前狀態**。每一步都重建快照的當前卡片*與*其鎖定集 L 與鎖定順序 Q。在非確定性隨機選取下的可重現性，完全由這些快照保證。

---

## 9. 版本歷史

| 版本 | 日期 | 變更 |
|------|------|------|
| 0.1 | 2026-03-25 | 初稿：概念與基本規則 |
| 0.2 | 2026-03-25 | 形式化定義、確認 FIFO 解鎖、排列約束、Prototype 完成 |
| 0.3 | 2026-03-25 | 修正機率模型（下降階乘）、定義候選池確定性排序、補充模糊匹配權衡分析 |
| 0.4 | 2026-03-26 | 新增插件系統架構與內建記憶（undo）插件規格 |
| 0.5 | 2026-03-30 | 候選池選取改為隨機（移除確定性循環）；起始卡片隨機化（可透過 startIndex 自訂）；seed 預設改為 Date.now() |
| 0.6 | 2026-03-30 | 新增 peek/peekAll 冪等性保證（快取機制）；新增 redo、canRedo、peek、peekAll 方法文件；UI 中 undo/redo 方向僅顯示箭頭 |
| 0.7 | 2026-06-24 | 修正 §8.2 以符合實作：`memory` 的 undo/redo 還原**完整狀態快照**（當前卡片＋鎖定），而非僅卡片；補充「相反方向→undo」與「重複方向→redo」提示（redo 現可在任意深度觸發）；說明 peek→navigate 目標一致性 |