小編精選 - 技術文章翻譯 · 09月01日

有人請我「幫我分得好看一點」，所以我試著定義了「好看一點」這件事

「不能幫我分一下嗎？」

你有被這樣拜託過嗎？

最困擾的是，沒有人定義那個「分得剛剛好」到底是什麼。

一問之下，通常會得到這類回答：

班表，盡量要公平
值班，盡量不要連在一起
審查人，盡量不要偏向同一個人
研修小組，盡量安排彼此不熟的人

全部都帶著「盡量」。

很可惜，只有「盡量」的話，沒辦法直接寫成程式。

沒辦法翻成 if，也沒辦法翻成 for。所以實作的人才會頭痛。

這篇文章要寫的，就是把那個「分得剛剛好」定義出來並解決的故事。

題材是公司內的 Shuffle Lunch（讓平常不一起工作的同事一起吃午餐的制度），把 80 人分成 3 到 4 人一組。

不過，本質上和排班表、值班表是一樣的。這次沒有用求解器或函式庫，只靠 Google Apps Script 寫出來。

先看結果

把 80 人每個月分成 3 到 4 人的小組。

如果隨機分配，上個月跟這個月重複到同一對人，大約每個月會出現 5 對。

也就是說，「明明是 Shuffle Lunch，結果又跟上個月一樣呢」這種情況，每個月大約會有 5 對。

這 5 對是怎麼算的（可跳過）80 人分成 4 人一組，共 20 組，所以同桌的配對數是 C(4,2)×20 = 120 對。
80 人能形成的總配對數是 C(80,2) = 3160 對。
特定兩人同組的機率是 120/3160 = 約 3.8%。
上個月的 120 對，這個月再次同桌的期望值是 120 × 3.8% = 約 4.6 對。

於是我把「分得剛剛好」真的定義出來後，結果變成這樣：

上個月重複的配對0 對（連續 12 個月）6 個月內曾見過的人再次同席0 對（連續 12 個月）計算時間約 2 秒小規模下與嚴格最優解一致140/140 case使用的求解器／函式庫沒有
原本隨機分配每個月大概會有 5 對重複，但把演算法做好之後，可以做到 0 對。

接下來會說，我把這個「剛剛好」翻譯成了什麼。

順帶一提，就算是隨機分配，也會出現偏差；值班表或排班表也一樣，常常會偏得超出「只是剛好」的直覺範圍。

把「盡量」分成兩種

把營運端提出的需求列出來，大概會像這樣：

申請不參加的人絕對不能排進去
每個小組都要是 3 人或 4 人
4 人小組要盡量多
盡量避開最近才一起吃過的人
不要讓同一事業部的人聚在一起

首先做的，是把這份清單分成兩類。

(A) 違反就會讓營運壞掉的。
(B) 違反了營運仍然能運作，但價值會下降的。

例如，如果把申請不參加的人排進去，那就是 bug，所以「申請不參加的人絕對不能排進去」屬於A。
相反地，就算有一組人跟上個月一樣，午餐還是能辦，所以「盡量避開最近才一起吃過的人」屬於B。

補充一下，(A) 稱為硬性約束，(B) 稱為軟性約束。

而且最重要的是：

軟性約束之間，可能彼此衝突。

把上個月一起吃過的兩個人拆開，結果又可能連帶讓同一事業部的兩個人坐在一起。

顧了這邊，就顧不到那邊。

所以我一開始就放棄了「全部都滿足」這種設計。這類問題很常見。（題外話：營運端大概也直覺知道不可能完美解掉，所以才會說「分得剛剛好」吧。）

「盡量多」，其實是硬性約束

在整理過程中，有一項讓人卡住的需求。

就是「4 人小組盡量多」。

盡量。怎麼看都像是軟性約束。

如果把它做成懲罰項，就會變成每多一個 3 人小組扣幾分之類的設計。

但其實不需要。

「最大化 4 人小組」換句話說，就是「最小化小組數」。

問題來了。
78 人要分成 3 到 4 人一組，想要「4 人小組盡量多」。

這條件需要最佳化嗎？

其實不需要。
78 人只能是「4 人×18 + 3 人×2」。

用公式表達就是這樣：

G = \left\lceil \frac{N}{4} \right\rceil, \qquad n_4 = N - 3G, \qquad n_3 = 4G - N

$n_4$ 是 4 人小組的數量，$n_3$ 是 3 人小組的數量。

N=80 時，G=20。剛好整除，所以是 4 人×20，3 人小組為 0。

如果有 2 人申請不參加，變成 N=78，G 仍然是 20，組合就變成 4 人×18 + 3 人×2。

這兩種情況都不可能有其他構成。根本沒有選擇空間對吧。

看起來像「盡量」，但其實是唯一決定的需求，意外地不少。
找到這種東西就賺到了，因為整個搜尋空間直接少掉一塊！

功能不是用來避開，而是用來讓它生不出來

再往下講一個做法上的重點。

既然知道是硬性約束，原本可以用超大的懲罰值，讓它實際上被避開——

但我沒有這樣做。

我直接讓系統不產生違反規則的分法。

const G = Math.ceil(N / 4);
const numFour = N - 3 * G;
const numThree = 4 * G - N;

const sizes = [];
for (let i = 0; i < numFour; i++) sizes.push(4);
for (let i = 0; i < numThree; i++) sizes.push(3);
// 後面只會照這個 sizes 來切分

搜尋演算法只會產生這種大小組合。

之後會提到的「一步操作」也只限制在不改變組別大小的操作。

這樣一來，硬性約束的違反在原理上就不會發生。

檢查流程也不用，重試也不用。

約束與其用懲罰，不如直接讓它不可能發生，會更好👌

剩下的「盡量」，改用不喜歡程度來計分

到這裡，硬性約束已經用結構解決了。那剩下的軟性約束怎麼辦？

做法很簡單。每發生一次不理想的事，就加一次分。

最後選總分最低的分法，就這麼簡單。

這個分數一般叫做「懲罰值」，簡單說就是 不喜歡程度的分數。

我把懲罰值定義如下：

事件懲罰值上個月同席的配對再次見面3 × 6 = 18同一事業部的配對每多 1 組8懲罰值本身沒有意義。重點是和其他項目相比時的比例。

「上個月的配對(18) > 事業部重複(8)」。

這個不等式，直接就是優先順序。需求訪談時說的「這個最優先」「再來是這個」，在這裡就變成數字了。

實際營運中如果被說「這個月要更重視混合不同事業部的人」，只要把 8 調高就行。

順帶一提，18 和 8 可以約分。改成 9 和 4，最後選出來的分法不會變。真正有作用的是比例。

把到這裡為止的內容表示成一個式子

就是對每個小組 $g$ 算分，再把全部加總。

\begin{aligned}
P = \sum_{g} \Bigl[\;
  & 3 \sum_{\{a,b\} \subset g} \mathrm{PairScore}(a,b) && \text{最近同席程度} \\
  +\; & 8 \sum_{d} \binom{k_d}{2} \;\Bigr]              && \text{同一事業部的配對數}
\end{aligned}

沒有什麼新東西，只是把前面的表格直接寫成公式而已。

式子裡的 3 是倍率。上個月同席是 6 分，所以乘 3 會變成 18。（為什麼是 6，後面會解釋。）

你可能會想：「左右從模型學習權重不就好了嗎？」

我也想過。

但後來放棄了。

每個月只有一次，拿來學習的資料一年只會增加 12 筆。

而且權重能讓人手動決定，本身也有營運上的價值。

因為當有人問「為什麼這兩個人同組」的時候，可以說得出理由。

對公司內部的機制來說，可解釋性有時比精準度更重要。

把同一事業部用「配對數」來數，而不是用「人數」

再介紹一個計數上的巧思。

我沒有用「同一事業部有 2 個人就扣 8 分」，而是改成「同一事業部的每一組配對扣 8 分」。

這樣一來：

2 人 → 1 組 → 8 分
3 人 → 3 組 → 24 分
4 人 → 6 組 → 48 分

人越聚越多，新增 1 人的代價就越大。只要改變計數方式，就能表現出「2 人還算可以，3 人以上就要盡量避免」這種營運直覺。

把「最近一起」用 0/1 來記錄，會損失資訊

「盡量避開最近的人」裡面的最近，也需要翻譯。

如果直接做成很直覺的實作，大概會像這樣：

if (先月同じグループだった) penalty += 18;

這樣雖然能動，但兩個月以前的資訊會完全消失。

所以我改成替過去每一次見面加上衰減係數再累加。

// decay(m) = max(0, 7 − m)   m 是幾個月前（上個月=1）
function decay_(monthsAgo) {
  return Math.max(0, 7 - monthsAgo);
}

上個月是 6 分。半年前是 1 分。超過 7 個月以前就是 0 分。

把這些加總後，就是 PairScore(a, b)。

「3 個月前只有同席 1 次（4 分）」比「上個月同席（6 分）」來得沒那麼痛。

越近的過去權重越重，越遠的過去就不算。

不要用門檻直接一刀切，而是讓它連續地作用，這點很重要。值班表裡「不要同一個人連著出現」也可以直接用這種形式。

一步一步交換，讓分數下降

結構上能決定的部分到這裡結束。剩下的交給「搜尋」。

把 80 人分成 4 人×20 組的方法有 7.3×10⁷² 種。不可能暴力搜尋。

所以我們只做這件事：

從現在的分法中挑 2 個人交換看看。如果分數下降，就採用。

一直重複，直到沒有能下降的交換。就這樣。

實際執行起來像這樣↓

Adobe Express - 画面収録 2026-08-24 20.45.03 (1)_crop940.gif

初始狀態是「和上個月完全相同的分組」。因為所有配對都帶著重見懲罰，所以一開始是 428 分。

接著一步一步，挑最有效的交換往下走。

428 → 288 → 184 → 107 → 55 → 37 → 19 → 16。7 步就降到底了。

可以看出，是依序選了最有用的步驟（−140、−104、−77、−52、……，最後是 −3）。

這就叫山登法

我做的事情其實只是「往比現在更好的方向，一步一步前進」。這種方法叫做局部搜尋，或者山登法（hill climbing）。

我準備的「一步操作」只有兩種：

跨組的1 對 1 交換
從 4 人組移到 3 人組的1 人移動

這兩種都不會破壞組別大小，所以硬性約束會一路自動維持。

// 1 對 1 交換: ga[i] ⇔ gb[j]
const delta = groupPenalty_(newA, ...) + groupPenalty_(newB, ...)
            - pen[a] - pen[b];      // ← 只重算受影響的兩組
if (delta < bestDelta) { bestDelta = delta; bestOp = {type:'swap', a, b, i, j}; }

順帶一提，80 人剛好時所有小組都是 4 人，所以「移動」這個操作根本不會用到。

等到有 2 人不參加、變成 78 人時，才會出現 2 個 3 人組，那時它才會派上用場。GIF 裡面出現兩次的「移動」就是這個。