┌─[ post.meta ]─ ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── ┐

技术 2026年8月6日

推角代码压缩算法技术报告

从 71 位定长位图到稳定组合编码：偶像大师推角集合的 62 进制稀疏压缩原理、信息论下界与稳定性设计。

└ ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── ┘

┌─[ post.md ]─ ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── ┐

给同好会做的推角代码页面经过三轮迭代，最终定型为一套「与名单总人数无关」的稳定组合编码。这篇报告记录它的设计动机、数学原理与验证过程。

问题

同好会的群友习惯在群名片里标注自己推的偶像。偶像大师全系列有 350+ 位偶像，把名字一个个列进名片显然不现实，于是想做一个工具：每个人点选自己的推角集合，生成一段短代码；其他人粘贴代码即可还原集合。

形式化地说：设偶像名单按固定顺序编号 0..N-1，推角集合就是 {0..N-1} 的一个稀疏子集。任务是把它编码成适合出现在群名片里的短字符串，并且解码无歧义。

第一版：位图 + 32 进制（71 位，太长）

最直接的方案是位图：每个偶像占 1 bit，选中为 1。N=354 时一共 354 bit，每 5 bit 合成 1 位 32 进制数字（0-9A-V），得到定长 71 位。

71 个字符放进群名片依然太长，而且对「只推 3～5 人」的绝大多数人来说，位图里 95% 以上都是 0，浪费严重。第一版很快被放弃。

第二版：组合编码（更短，但会漂移）

位图的本质问题是定长。一个 $k$ 元子集只需要 $\log_2 C(N,k)$ 比特信息，稀疏集合的 $k$ 很小，理应可以短得多。

于是第二版用组合数系统（combinadic / combinatorial number system）把子集整体映射为一个整数：

\mathrm{rank} = \sum_{j=0}^{k-1} C(N, j) + \sum_{j=0}^{k-1} C(s_j, j+1)

第一项是「所有小于 k 元的子集个数」（按大小排位），第二项是「该 k 元组合在字典序下的排名」。这个整数再用 62 进制（0-9A-Za-z）变长表示。

效果很好：推 5 人只要 5～6 个字符，推 10 人 10～11 个字符。但这里埋了一个雷——第一项依赖总人数 $N$ 。

偶像大师还在不断出新角色。模拟验证：5 人集合在 $N=357$ 时生成的代码 MBDmy1，把 $N$ 改成 358 后同一段代码解出的集合变成了完全不同的 5 人：

总人数 N	同一代码解出的序号
357	3, 17, 99, 200, 300
358	13, 51, 66, 194, 300

这意味着以后每实装一位新偶像，群里所有人分享过的旧代码含义全部变化。对于用来长期交流的代码，这是不可接受的。

第三版：稳定组合编码（当前方案）

修复思路很直接：让编码只依赖选中的序号本身，与 N 无关。

数学原理

组合数系统有一个优雅的性质：任意 $k$ 元升序组合 $s_1 < s_2 < \dots < s_k$ 可以唯一表示为一个「colex 秩」：

\mathrm{rank}_k = \sum_{j=0}^{k-1} C(s_{j+1},\, j+1)

这个数只取决于 $s_j$ 的取值，完全不包含 $N$ 。解码时用贪心反向求解：从 $j=k$ 到 1，每次找最大的 $x$ 使 $C(x,j) \le r$ ，即可唯一还原每个 $s_j$ 。

由于 $\mathrm{rank}_k$ 与 $N$ 无关，编码天然稳定——前提是序号本身不变。因此配套两条名单策略：

系列顺序固定，系列内首次生成时按拼音排序；
新偶像只追加在名单末尾，已有偶像永不重排（生成脚本采用合并模式，而不是每次重新排序）。

编码格式

最终格式为：

代码 = k 前缀 + base62(rank_k)

$k \le 61$ ：前缀 1 个字符（ALPH[k]）；
$k > 61$ ：以 - 开头，再接 2 位 62 进制 $k$ ；
空集合："0"。

核心实现（BigInt 精确计算，避免超过 2^53 的精度损失）：

// 组合数表：C[n][r]，Pascal 三角，BigInt
const binom = (n: number, r: number) => (r < 0 || r > n ? 0n : C[n][r]);

// 编码：k 前缀 + combinadic 秩
function encode(idxs: number[]): string {
  const k = idxs.length;
  if (k === 0) return "0";
  let rank = 0n;
  for (let j = 0; j < k; j++) rank += binom(idxs[j], j + 1);
  return (k <= 61 ? ALPH[k] : "-" + base62(k)) + base62(rank);
}

// 解码：贪心反解每个序号
function decode(code: string): number[] {
  // 解析出 k 与 rank …
  const out: number[] = [];
  let rem = rank;
  for (let j = k; j >= 1; j--) {
    let lo = j - 1, hi = N - 1; // 二分找最大 x 使 C(x, j) ≤ rem
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (binom(mid, j) <= rem) lo = mid; else hi = mid - 1;
    }
    out.push(lo);
    rem -= binom(lo, j);
  }
  return out;
}

信息论下界与长度

62 进制每字符携带 $\log_2 62 \approx 5.95$ bit。表示一个 $k$ 元子集至少需要 $\log_2 C(N,k)$ bit，再加上人数 $k$ 本身的信息，这就是稳定编码的代价——比不稳定的第二版大约多 1 个字符，属于理论下限，无法再省。

实测最长长度（N=357）：

人数	1	2	3	4	5	6	7	8	9	10	20	30	50	100
最长字符	3	4	5	6	7	8	9	10	11	12	20	26	36	54

常见的「推 3～8 人」场景在 5～10 个字符内即可表达。

验证

200 轮随机集合（稀疏/密集混合）编码→解码往返一致；
用 N+3 模拟未来新增 3 位偶像，200 轮全部保持同一代码解码出同一集合；
边界用例：空集（0）、k=61（单字符前缀 z）、k=62（- 转义）、全选 357 人（4 个字符）均正确；
解码校验：非法字符、序号越界等情况会明确报错。

局限与后续

代码大小写敏感（62 进制需要区分 a 与 A），分享时建议直接复制粘贴；
名单只能追加、不能重排，未来加入新系列时需放到列表末尾；
页面另外实现了昵称/别号/集合检索（如 ktn、cosmo），方便按圈内称呼批量选择，这属于检索功能，与本压缩算法相互独立。

代码与数据都在 scripts/imas-idols.mjs 的仓库中，欢迎指正。