python - 生成恰好有 1 个元素与组中其他集合相交的集合的算法

Question

有一种称为 Maekawa 的算法，用于将消息发送到特定的请求集 ( http://courses.cs.vt.edu/cs5204/fall99/Supplemental/ProblemSet8.html )

我对生成请求集的算法感兴趣，其值 K=3(集合中有 3 个元素)，N=7(7 个这样的集合)

每个集合与其他集合相交时，应产生“一个”公共(public)值。如何通过算法生成它

Answer 1

这些结构是在设计理论中研究的，设计理论是组合学的一部分。您也许可以使用强力搜索，但这不会让您走得太远。

集合的集合，使得任何两个集合的交集的大小为 1 是 linear space 的对偶。 ，其中每两个点确定一条唯一的线。生成线性空间的最简单方法是使用有限域而不是实数坐标来概括坐标几何。例如，Fano plane是具有 2 个元素的场上的投影平面。您可以让点对应于长度为 3 的 7 个非零二进制 vector ，其中线对应于总和为 (1,1,1) 的三元组，其中每个坐标添加 mod 2。还有其他描述，例如 {{i , i+1, i+3}} 其中 i 的范围从 0 到 6，每个元素都减少 mod 7。射影平面与射影平面对偶，具有相同数量的点和线，因此这已经是 a 的对偶线性空间，每对直线相交于一点。 Fano 平面可能正是您想要的具有这些参数的平面。

整数模质数 p 上的仿射平面比射影平面更容易描述。这些点是整数 mod p 的元素对。线可以描述为 ax+by=c 的解，其中所有算术都完成 mod p 并且 a 和 b 不能同时为 0。当 p=3 时，有 9 个点和 12 条线。通过每个点，有 4 条线，每个斜率各一条:0、1、2 和垂直。您想要的结构是对偶的，因此集合对应于平面中的点，元素对应于包含这些点的线。这给出了一个包含 12 个元素和 9 个大小为 4 的集合的结构。

游戏中Set ，您尝试识别整数 mod 3 上的仿射 4 空间中的行，尽管没有那么多单词。这是一个有 81 个点和穿过每个点的 40 条线的线性空间，因此它与具有 1080 个元素和 81 个子集(由 40 个点组成)的结构对偶，因此每对子集在一个元素中相交。