背景与示例 #

我是计算机科学背景，最近在研究一组节点上的正交分拆（要求子集大小固定且统一），且希望构造方法能随分拆数和节点数扩展。

举个具体例子：在集合${0,...,8}$上，把数字排成3×3的环面网格（支持“环绕”），分别取行、列和两条对角线，就能得到4个满足要求的正交分拆：

• ${{0,1,2},{3,4,5},{6,7,8}}$
• ${{0,3,6},{1,4,7},{2,5,8}}$
• ${{0,4,8},{1,5,6},{2,3,7}}$
• ${{2,4,6},{1,3,8},{0,5,7}}$
  这些分拆满足统一子集大小+正交性的要求。

已有的研究进展 #

我发现这类问题和组合设计的变体密切相关：

• 首先找到了MOLS（正交拉丁方），了解到可以通过正交数组将MOLS转换为“网”，这看起来是我需求的一个子类。我还找到代码可以轻松生成素数$n$对应的MOLS($n$)。
• 对于素数$n \in \mathbb{N}$，我可以生成$(n-1)$个MOLS，进而转换得到$(n+1)$个分拆，对应$n^2$个节点，每个子集大小为$n$，分拆满足正交性。
• 后来偶然接触到社交高尔夫球手问题，最终找到了可解分组可设计（RGDD）——这完全匹配我要的定义。具体来说，我关注的是$\lambda=1$的RGDD（不同分拆的子集最多交于1个元素），更准确地说，是固定单元素$K$（统一块大小）但可变$\nu$（元素数量）的RGDD族。

核心疑问 #

由于我没有组合数学或统计学的深厚背景，相关概念和名称繁多容易混淆，想确认自己有没有覆盖所有有用/相关的存在性和构造结论：

• 除了基于MOLS/有限域的素数构造方法，有没有已知的有效、系统的方法来构造这类RGDD？
• 有没有现成的算法或实现可以直接生成我要的RGDD，且支持素数幂的情况？
• 对于（素数幂以外的）合数，RGDD的存在性和构造有什么已知结论？

我主要关注可构造的结果（最好不需要深入组合数学或有限域理论就能实现），但存在性/非存在性结论也能帮我理清方向。

关于递归构造的额外问题 #

我自己摸索出了一个递归构造方法：以“基础RGDD”（比如从MOLS得到的）为起点，生成更大的节点集。例如，用3的基础RGDD（对应$3^{2$个节点的示例），可以生成任意$i\in\mathbb{N}$的RGDD：节点数为$3}i$，包含$3^{{i-1}$个组，每个组有$3}{i-1}$个大小为3的块。

我还没完成严格证明，只是针对不同参数做了测试，但看到一篇论文的定理2.2后，发现我的方法看起来像是迭代的“RGDD乘法”（实际是幂运算），参数也符合定理预期。

想请教几个问题：

• 这个构造方法是已知的、常识性的，还是trivial的？有没有论文详细解释过这类构造的实践方法，或者有现成的库/实现？
• 如果我把具体算法写出来并尝试证明，会有价值吗？我是先想到构造方法才看到那篇论文的，还不确定它和论文证明步骤的关联。

基于有限域的构造对于素数幂应该能得到完整的分拆集（理论上可以得到$p^{k+1$个分拆？来自$p}k{-}1$个MOLS($p$)），但我完全理解不了也实现不了，而且没见过通用的实现；另外这个方法会导致块大小越来越大，而我希望块大小保持固定。所以我觉得换一种构造方法可能更有意义。

如果这个方法是新的且非平凡的，可能会激励我进一步完善并写出来（甚至尝试推广）。

希望能得到一些引导，帮我理清这个组合数学领域的思路！

备注：内容来源于stack exchange，提问作者apirogov