每日算法 — 使用java实现Polya计数定理：对称群作用下的组合计数与项链着色

一、问题背景

在组合数学中，我们经常遇到这样的问题：用 $m$ 种颜色给 $n$ 颗珠子的项链着色，考虑旋转等价后有多少种不同的着色方案？如果还考虑翻转等价呢？

直接枚举所有 $m^n$ 种着色再判断等价性效率太低。Polya计数定理 提供了一种 elegant 的解决方案，它通过对称群的循环结构来一次性计算不等价的着色数。

二、核心思想

Polya计数定理是Burnside引理的推广形式。对于一个置换群 $G$ 作用在集合 $X$ 上，不等价的着色数等于群中每个元素的循环指标多项式在 $m$ 处的取值平均：

$$P_G(m) = \frac{1}{|G|} \sum_{g \in G} m^{c(g)}$$

其中 $c(g)$ 表示置换 $g$ 分解为不相交循环后的循环个数。

对于更一般的情况，如果每种颜色有权重，我们使用 循环指标多项式 ：

$$Z(G) = \frac{1}{|G|} \sum_{g \in G} \prod_{k=1}^{n} x_k^{c_k(g)}$$

其中 $c_k(g)$ 是置换 $g$ 中长度为 $k$ 的循环个数。

三、Java实现

3.1 置换的循环分解

import java.util.*;

/**
 * Polya计数定理实现
 * 用于计算对称群作用下的不等价着色数
 */
public class PolyaCounting {

    /**
     * 计算一个置换的循环分解
     * @param perm 置换，perm[i] 表示 i 映射到的位置
     * @return 每个循环的长度列表
     */
    public static List<Integer> cycleDecomposition(int[] perm) {
        int n = perm.length;
        boolean[] visited = new boolean[n];
        List<Integer> cycles = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            // 从一个未访问点开始追踪循环
            int current = i;
            int cycleLen = 0;
            while (!visited[current]) {
                visited[current] = true;
                current = perm[current];
                cycleLen++;
            }
            cycles.add(cycleLen);
        }
        return cycles;
    }

    /**
     * 计算循环指标多项式中的单项式贡献
     * 返回各长度循环的个数
     */
    public static Map<Integer, Integer> cycleIndex(int[] perm) {
        List<Integer> cycles = cycleDecomposition(perm);
        Map<Integer, Integer> count = new HashMap<>();
        for (int len : cycles) {
            count.put(len, count.getOrDefault(len, 0) + 1);
        }
        return count;
    }

3.2 necklace 的旋转群

    /**
     * 生成 n 颗珠子的项链旋转群的所有置换
     * 旋转群 C_n 包含 n 个元素：旋转 0, 1, ..., n-1 个位置
     */
    public static List<int[]> cyclicGroup(int n) {
        List<int[]> group = new ArrayList<>();
        for (int shift = 0; shift < n; shift++) {
            int[] perm = new int[n];
            for (int i = 0; i < n; i++) {
                perm[i] = (i + shift) % n;
            }
            group.add(perm);
        }
        return group;
    }

    /**
     * 生成二面体群 D_n（包含旋转和翻转）
     * D_n 有 2n 个元素
     */
    public static List<int[]> dihedralGroup(int n) {
        List<int[]> group = new ArrayList<>();

        // 添加所有旋转
        group.addAll(cyclicGroup(n));

        // 添加所有翻转
        // 翻转类型1：沿穿过相对顶点（或边中点）的轴翻转
        for (int axis = 0; axis < n; axis++) {
            int[] perm = new int[n];
            for (int i = 0; i < n; i++) {
                // 关于穿过 axis 和 axis+n/2 的轴翻转
                perm[i] = (2 * axis - i + n) % n;
            }
            group.add(perm);
        }
        return group;
    }

3.3 Polya定理核心计算

    /**
     * 使用Polya计数定理计算不等价着色数
     * @param group 置换群的所有元素
     * @param colors 颜色种数
     * @return 不等价着色方案数
     */
    public static long polyaCount(List<int[]> group, int colors) {
        long sum = 0;
        for (int[] perm : group) {
            List<Integer> cycles = cycleDecomposition(perm);
            // 每个循环内的所有位置必须同色，所以有 colors^cycles 种选择
            sum += pow(colors, cycles.size());
        }
        return sum / group.size();
    }

    /**
     * 快速幂计算
     */
    private static long pow(long base, int exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) result *= base;
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    /**
     * 使用循环指标多项式计算带权着色数
     * 可以指定每种颜色的具体权重
     */
    public static long polyaCountWeighted(List<int[]> group, 
                                          Map<String, Long> colorWeights) {
        long sum = 0;
        long totalWeight = colorWeights.values().stream().mapToLong(Long::longValue).sum();

        for (int[] perm : group) {
            Map<Integer, Integer> cycleCount = cycleIndex(perm);
            long term = 1;

            // 对每个循环长度 k，计算 (sum of w_i^k) ^ c_k
            for (Map.Entry<Integer, Integer> entry : cycleCount.entrySet()) {
                int cycleLen = entry.getKey();
                int count = entry.getValue();

                long weightSumK = 0;
                for (long w : colorWeights.values()) {
                    weightSumK += pow(w, cycleLen);
                }
                term *= pow(weightSumK, count);
            }
            sum += term;
        }
        return sum / group.size();
    }

3.4 完整测试与演示

    public static void main(String[] args) {
        int n = 6;      // 6颗珠子
        int m = 3;      // 3种颜色

        System.out.println("=== Polya计数定理演示 ===");
        System.out.println("项链问题：" + n + "颗珠子，" + m + "种颜色\n");

        // 1. 仅考虑旋转等价（循环群 C_n）
        List<int[]> cyclic = cyclicGroup(n);
        long cyclicCount = polyaCount(cyclic, m);
        System.out.println("仅旋转等价：" + cyclicCount + " 种方案");

        // 2. 考虑旋转和翻转等价（二面体群 D_n）
        List<int[]> dihedral = dihedralGroup(n);
        long dihedralCount = polyaCount(dihedral, m);
        System.out.println("旋转+翻转等价：" + dihedralCount + " 种方案");

        // 3. 验证：枚举所有方案（仅适用于小规模）
        if (n <= 8) {
            long bruteForce = bruteForceCount(n, m, dihedral);
            System.out.println("暴力验证：" + bruteForce + " 种方案");
            System.out.println("结果一致：" + (dihedralCount == bruteForce));
        }

        // 4. 展示每个群元素的循环结构
        System.out.println("\n=== 二面体群 D_" + n + " 的循环分解 ===");
        for (int i = 0; i < dihedral.size(); i++) {
            List<Integer> cycles = cycleDecomposition(dihedral.get(i));
            System.out.println("置换 " + i + ": 循环结构 " + cycles);
        }
    }

    /**
     * 暴力枚举验证（仅用于小规模测试）
     */
    public static long bruteForceCount(int n, int colors, List<int[]> group) {
        int total = 1;
        for (int i = 0; i < n; i++) total *= colors;

        boolean[] equivalent = new boolean[total];
        long count = 0;

        for (int mask = 0; mask < total; mask++) {
            if (equivalent[mask]) continue;
            count++;

            // 标记所有等价的着色
            for (int[] perm : group) {
                int newMask = applyPermutation(mask, perm, colors);
                equivalent[newMask] = true;
            }
        }
        return count;
    }

    private static int applyPermutation(int mask, int[] perm, int colors) {
        int n = perm.length;
        int[] coloring = new int[n];
        int tmp = mask;
        for (int i = n - 1; i >= 0; i--) {
            coloring[i] = tmp % colors;
            tmp /= colors;
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            result = result * colors + coloring[perm[i]];
        }
        return result;
    }
}

四、复杂度分析

其中 $n$ 为珠子数，$m$ 为颜色数，$|G|$ 为群的大小。

五、扩展应用

Polya定理的应用远不止项链着色：
– 分子结构计数：化学中不同同分异构体的计数
– 图论：计算不同构的图的数量
– 密码学：S盒的对称性分析
– 电路设计：考虑旋转对称的电路板布局

掌握Polya定理，你就拥有了一把处理对称性计数问题的利器。