求生成n个参与者的唯一循环赛的Python方案及计数公式

一、唯一赛果数量的计算公式 #

n个参与者的循环赛对应竞赛图（每对顶点间有且仅有一条有向边的有向图），不同构的竞赛图数目即为本质不同的赛果数量。这个数目可以通过Burnside引理计算：

$$T(n) = \frac{1}{n!} \sum_{\sigma \in S_n} 2^{f(\sigma)}$$

其中：

• $S_n$是n个元素的对称群（所有顶点置换的集合）
• $f(\sigma)$的计算规则：
  1. 若置换$\sigma$的循环分解中存在偶数长度的循环，则$2^{f(\sigma)} = 0$（不存在在该置换下不变的竞赛图）
  2. 若$\sigma$的所有循环长度均为奇数，设分解为$m$个长度分别为$k_1,k_2,...,k_m$的循环，则：
     $$f(\sigma) = \binom{m}{2} + \sum_{i=1}^m \frac{k_i - 1}{2}$$
     其中$\binom{m}{2}$是不同循环对的数量（每对循环间的边方向需一致，对应一个选择），$\frac{k_i-1}{2}$是单个奇数循环内部的独立边方向选择数。

这个序列也对应OEIS中的A000568，前几项为：

• n=1: 1
• n=2: 1
• n=3: 2
• n=4: 4
• n=5: 12
• n=6: 56

二、高效遍历唯一赛果的Python实现 #

直接生成所有可能的赛果再去重（检查同构）效率极低（n=15时总共有$2^{105}$种可能），因此需要生成每个同构类的标准代表元，避免重复。

方法1：基于图同构检测的去重（适合n≤8） #

利用networkx库的图同构工具，将每个竞赛图转换为标准形，再去重：

import networkx as nx

def tournament_from_bitfield(n, bitfield):
    """将bitfield转换为竞赛图的networkx有向图对象"""
    g = nx.DiGraph()
    g.add_nodes_from(range(n))
    edge_idx = 0
    for i in range(n):
        for j in range(i+1, n):
            if bitfield & (1 << edge_idx):
                g.add_edge(i, j)
            else:
                g.add_edge(j, i)
            edge_idx += 1
    return g

def get_canonical_bitfield(g):
    """返回竞赛图的标准形bitfield（同构类的最小字典序表示）"""
    # 获取Nauty算法生成的标准顶点标号
    canonical_labels = nx.algorithms.isomorphism.canonical_label(g)
    # 按标准标号排序顶点
    sorted_nodes = sorted(g.nodes(), key=lambda x: canonical_labels[x])
    n = g.number_of_nodes()
    canon_bitfield = 0
    edge_idx = 0
    for i in range(n):
        u = sorted_nodes[i]
        for j in range(i+1, n):
            v = sorted_nodes[j]
            if g.has_edge(u, v):
                canon_bitfield |= (1 << edge_idx)
            edge_idx += 1
    return canon_bitfield

def generate_unique_tournaments(n):
    """生成所有唯一竞赛图的标准形bitfield集合"""
    total_pairs = n * (n-1) // 2
    unique_tournaments = set()
    # 遍历所有可能的赛果（仅适合n≤8，n=8时需遍历2^28=2.68亿次，耗时较长）
    for bitfield in range(0, 1 << total_pairs):
        tourney = tournament_from_bitfield(n, bitfield)
        canon = get_canonical_bitfield(tourney)
        unique_tournaments.add(canon)
    return unique_tournaments

# 示例：生成n=3的唯一赛果
unique_3 = generate_unique_tournaments(3)
print(f"n=3时唯一赛果数量：{len(unique_3)}")  # 输出2，符合预期

方法2：回溯生成标准代表元（适合更大的n） #

对于n≥9，上述方法无法遍历所有可能，需采用回溯法直接构造无更小同构形式的竞赛图：

1. 按顶点顺序逐个添加，每次添加第k个顶点时，确定它与前k-1个顶点的边方向
2. 确保当前构造的k顶点竞赛图不存在任何置换，能生成字典序更小的同构竞赛图
3. 递归完成所有顶点的添加，得到所有唯一赛果的代表元

这种方法避免了生成重复结构，效率远高于全遍历，但实现复杂度较高，需结合置换对称性的剪枝逻辑。

内容的提问来源于stack exchange，提问作者Ctenochaetus