每日算法 — 使用java实现形色（Set）：模三向量判等与位压缩DP最大分解

一、把卡牌变成 F₃ 上的向量

形色（对应英文卡牌游戏 Set）的牌面由四个独立属性构成，每个属性恰好三种取值：

一副牌共 3⁴ = 81 张，恰好是四维三值网格的全部格点。一组”形色”（Set）的定义是：三个属性，每张牌在该属性上要么三者全同、要么三者全不同。

这个定义有一个极其漂亮的代数等价形式。把每张牌编码为向量 v ∈ F₃⁴（每个坐标取 0/1/2），三个牌 a, b, c 构成 Set 当且仅当

a + b + c ≡ (0, 0, 0)  (mod 3)

原因是：坐标上 {0,0,0} 和为 0、{1,1,1} 和为 3 ≡ 0、{2,2,2} 和为 6 ≡ 0，而任何”两同一异”的组合和都不为 0（例如 1+1+2 = 4 ≡ 1）。于是“全同或全不同” ⟺ “模三和为零”，判定从 4 个属性的分支判断塌缩成一次向量加法。

更妙的是：给定任意两张不同的牌 a, b，第三张牌 c 是唯一确定的——c = (-a-b) mod 3，且必然是一张合法牌（坐标必在 0..2 内）。这条性质意味着任意两张不同的牌恰好属于唯一一个 Set，也解释了为什么一副 81 张牌里 Set 的总数恰好是 C(81,2)/3 = 1080。

二、编码与判定

public final class Card {
    public static final int ATTRS = 4, VALUES = 3;

    /** 用四维三值向量编码，各分量范围 0..2 */
    public final int a, b, c, d;

    public Card(int a, int b, int c, int d) {
        this.a = a; this.b = b; this.c = c; this.d = d;
    }

    /** 编码成 0..80 的整数（三位一组） */
    public int code() {
        return a * 27 + b * 9 + c * 3 + d;
    }

    public static Card fromCode(int code) {
        return new Card(code / 27, (code / 9) % 3, (code / 3) % 3, code % 3);
    }

    /** 给定两张牌，推出第三张：c = (-a-b) mod 3，逐分量 */
    public static Card third(Card x, Card y) {
        int na = (6 - x.a - y.a) % 3;   // 等价于 (3 - (x+y)%3) % 3
        int nb = (6 - x.b - y.b) % 3;
        int nc = (6 - x.c - y.c) % 3;
        int nd = (6 - x.d - y.d) % 3;
        return new Card(na, nb, nc, nd);
    }

    /** 判定三张牌是否构成 Set */
    public static boolean isSet(Card x, Card y, Card z) {
        return (x.a + y.a + z.a) % 3 == 0
            && (x.b + y.b + z.b) % 3 == 0
            && (x.c + y.c + z.c) % 3 == 0
            && (x.d + y.d + z.d) % 3 == 0;
    }

    @Override public String toString() {
        return "(" + a + "," + b + "," + c + "," + d + ")";
    }
}

third 里的 (6 - x - y) % 3 值得说明：x, y ∈ [0,2]，故 x+y ∈ [0,4]，6-x-y ∈ [2,6]，取模 3 后必落在 [0,2]——Java 的 % 对正数不会返回负数，所以这一步是安全的。若坐标允许负数，就必须补一次 +3 再取模。

三、枚举全部 Set：哈希 O(n²) 而非三重循环

桌面上有 n 张牌（通常 12 张，最多可到 15~18）。三重循环 O(n³) 对 12 张只是 220 次判定，随便写都行；但若做”牌局可行性分析”（枚举 81 张全牌的所有 Set），O(81³) = 531441 也不算大。真正需要优化的是“给定牌面，找出所有 Set” 在移动端每帧调用的场景，以及“找出至少包含某张牌的所有 Set” 这类子问题。

标准解法是 O(n²) 哈希：

public final class SetFinder {
    /** 返回所有构成 Set 的三元组（下标） */
    public static java.util.List<int[]> findAll(java.util.List<Card> cards) {
        java.util.List<int[]> result = new java.util.ArrayList<>();
        int n = cards.size();
        java.util.Map<Integer, Integer> present = new java.util.HashMap<>();
        for (int i = 0; i < n; i++) present.put(cards.get(i).code(), i);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Card need = Card.third(cards.get(i), cards.get(j));
                Integer k = present.get(need.code());
                // 必须要求 k > j，保证每组只报一次，且不会出现 i=j=k
                if (k != null && k > j) {
                    result.add(new int[]{i, j, k});
                }
            }
        }
        return result;
    }
}

这里 k > j 是去重的关键。由于第三张牌唯一，”任意两张 → 唯一第三张”的映射保证了三元组只会被枚举到一次（从其最小的两个下标出发），不需要额外的 Set<String> 去重，节省了对象分配开销。

顺带可得一条硬结论：若桌面有 n 张牌且牌不重复，则 Set 数量上界为 C(n,2)/3。12 张时上界 22，实际通常个位数——这就是为什么规则要求”12 张无解则补牌”，无解本身就是大概率事件。

四、最大不交集：为什么贪心会输

多人对局中，每次找到 Set 就把三张牌取走、补三张新牌。于是产生一个真问题：当前牌面最多能连取几组 Set？ ——即把卡牌集合划分成尽可能多的互不相交的 Set。

这是一个 3-Set Packing 问题，属于 NP-hard（可归约到三维匹配 3DM）。贪心在这里会稳定地输：优先选”最容易找到”的 Set，往往会把关键的公共牌烧掉，导致后续崩盘。反例很容易构造——一个被 3 个 Set 共享的”枢纽牌”，贪心若先用掉它，剩下的牌就再也拼不出 Set。

位压缩 DP：n ≤ 20 时的精确解

当桌面上限 12~15 张（或做离线最优分析时到 20 张），用位掩码 DP 可以拿到精确最优：

dp[mask] = max{ 1 + dp[mask \ triple] | triple ⊆ mask 且 triple 是 Set }

这里 mask 是”还未取的牌”集合。状态数 2^n，n = 15 时是 32768，配上前置枚举出的 Set 列表，整体毫秒级。

public final class PackingDP {
    /** 返回最大可连取的 Set 组数 */
    public static int maxDisjointSets(java.util.List<Card> cards) {
        int n = cards.size();
        if (n < 3) return 0;

        // 1. 先把所有 Set 的具体三元组枚举成位掩码
        java.util.List<Integer> triples = new java.util.ArrayList<>();
        java.util.Map<Integer, Integer> present = new java.util.HashMap<>();
        for (int i = 0; i < n; i++) present.put(cards.get(i).code(), i);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Card need = Card.third(cards.get(i), cards.get(j));
                Integer k = present.get(need.code());
                if (k != null && k > j) {
                    triples.add((1 << i) | (1 << j) | (1 << k));
                }
            }
        }
        if (triples.isEmpty()) return 0;

        // 2. dp[mask] = 在 mask 这张"剩余牌"集合上还能再取几组
        int[] dp = new int[1 << n];
        java.util.Arrays.fill(dp, -1);
        dp[(1 << n) - 1] = 0;                       // 从满集出发，向后取

        // 3. 逆序推进：mask 从大到小，确保子状态先被算好
        for (int mask = (1 << n) - 1; mask >= 0; mask--) {
            if (dp[mask] < 0) continue;
            for (int t : triples) {
                if ((mask & t) != t) continue;      // 三元组必须完整落在 mask 内
                int rest = mask ^ t;
                if (dp[rest] < dp[mask] + 1) {
                    dp[rest] = dp[mask] + 1;
                }
            }
        }
        // 空集（或不含任何完整三元组的状态）中的最大值即答案
        int best = 0;
        for (int v : dp) best = Math.max(best, v);
        return best;
    }
}

这段实现有一个易错点：由于 rest = mask ^ t 必然小于 mask（异或只会把置位清零），必须让 mask 从大到小迭代，才能保证写入 dp[rest] 时它的所有上游来源都已处理过。若误用升序，dp[mask] 在被读取时还是初始的 -1，整条链会断掉、答案系统性偏小甚至为 0。最后的 max 扫描则是为了兼容”剩余牌里再也凑不出三元组”的状态——此时 dp[rest] 停在某个中间值，而那才是真实可取组数。

O(2^n · T) 的复杂度在 n = 15、T ≈ 20 时约 65 万次操作，完全可接受。若 n = 20（2²⁰ = 1048576 状态 × 最多 100 个三元组 ≈ 1 亿次），在移动端需要拆成多帧、或者改用”按块分治 + 记忆化”。

五、实时校验：玩家点选的最优反馈

玩家点选三张牌时，游戏需要即时给出”是否合法 + 错在哪”。朴素做法是逐个属性比较，四次分支；用向量法可以做得更优雅：先算 s = (a+b+c) mod 3，再检查 s 是否全零。若不为零，s 的非零分量恰好就是违反的属性，可以直接高亮提示——这比”逐个属性判 4 次”省掉一轮循环，也让错误反馈的语义精确到属性级。

public final class Validator {
    /** 返回 null 表示合法，否则返回违反的属性下标 */
    public static int[] violated(Card x, Card y, Card z) {
        int[] s = {
            (x.a + y.a + z.a) % 3,
            (x.b + y.b + z.b) % 3,
            (x.c + y.c + z.c) % 3,
            (x.d + y.d + z.d) % 3
        };
        int cnt = 0;
        for (int v : s) if (v != 0) cnt++;
        if (cnt == 0) return null;
        int[] bad = new int[cnt];
        int p = 0;
        for (int i = 0; i < 4; i++) if (s[i] != 0) bad[p++] = i;
        return bad;
    }
}

六、完整工程结构

set-game/
├── pom.xml
└── src/main/java/com/example/setgame/
    ├── Card.java        // 四维三值编码与判定
    ├── SetFinder.java   // 哈希枚举全部 Set
    ├── PackingDP.java   // 位掩码 DP 最大不交集
    ├── Validator.java   // 实时合法性反馈
    └── Demo.java

public final class Demo {
    public static void main(String[] args) {
        // 1. 全牌 81 张，验证 Set 总数应为 C(81,2)/3 = 1080
        java.util.List<Card> all = new java.util.ArrayList<>();
        for (int code = 0; code < 81; code++) all.add(Card.fromCode(code));
        int total = SetFinder.findAll(all).size();
        System.out.println("全副 81 张的 Set 总数 = " + total);   // 1080

        // 2. 12 张手牌：找出所有 Set
        java.util.List<Card> hand = new java.util.List.of(
                Card.fromCode(0),  Card.fromCode(1),  Card.fromCode(2),
                Card.fromCode(3),  Card.fromCode(4),  Card.fromCode(5),
                Card.fromCode(9),  Card.fromCode(10), Card.fromCode(11),
                Card.fromCode(13), Card.fromCode(26), Card.fromCode(40));
        java.util.List<int[]> sets = SetFinder.findAll(hand);
        System.out.println("手牌 Set 数量 = " + sets.size());

        // 3. 最大不交集
        System.out.println("最大可连取组数 = " + PackingDP.maxDisjointSets(hand));

        // 4. 实时校验
        int[] bad = Validator.violated(hand.get(0), hand.get(1), hand.get(5));
        System.out.println("校验结果（null 为合法）= " +
                (bad == null ? "合法" : java.util.Arrays.toString(bad)));
    }
}

七、复杂度与三条结论

结论一，模三表示是本问题的”正确的坐标系”。 用四个布尔属性分别判”全同/全不同”，代码量至少翻三倍，而且错误提示只能笼统说”不合法”；换成 F₃ 向量后，”和为零”既是判定又是诊断，这是抽象带来的直接收益。

结论二，”任意两牌唯一确定第三牌”这条性质支撑了几乎所有高效算法。 O(n²) 枚举、C(n,2)/3 的计数上界、以及”无解即大概率”的规则设计，全部由它推出。识别出这种”闭包性质”，往往比优化常数更重要。

结论三，连取阶段必须上精确算法。 贪心在 3-Set Packing 上会稳定地输，而玩家对”明明还有 Set 却提示补牌”的容忍度为零。12~15 张的规模下位掩码 DP 成本极低，没有理由退而求其次用启发式。

补充一个工程细节：present 哈希表要求牌不重复。若业务允许重复牌（某些变体允许牌面同构、仅图案镜像不同），Map<Integer,Integer> 会覆盖同码牌，导致漏解。此时应改成 Map<Integer, List<Integer>>，并在枚举时对每个候选下标逐一生成三元组，代价从 O(n²) 升到 O(n²·k)（k 为同码牌数），但正确性无虞。