如何选择合适的图结构检测集合列表中的数值循环以避免笛卡尔积重复？

我把自己的答案设为了最佳答案，因为它正好实现了我想要的功能，其他有同样需求的人可以从这个思路入手。不过我也很期待看到更优的解法——比如能高效生成所有循环（比如示例里那种）的Python实现，如果有更好的答案我也会欣然更改选择。以下是最初的问题描述：

给定一组集合，比如：

sets=[{1,2},{2,3},{1,3}]

用itertools.product(*sets)生成笛卡尔积时，(1,2,3)会被生成两次，分别是(1,2,3)和(2,3,1)，根源就在于这里存在循环结构。如果没有循环，哪怕集合之间有大量交集，也不会出现重复的笛卡尔积结果。

这里说的循环是指：从某个集合里的元素A出发，先到同集合内的元素B，再跨集合到另一个包含B的集合，最终能连回A；或者通过中间元素C间接连回A。比如1>2--2>3--3>1，其中--表示跨集合的元素移动，>表示同一集合内的元素跳转。最小的循环是两个集合共享一对元素的情况，比如a>b--b>a。（后来觉得用{a}-b-{a}这种标记方式更清晰）另外，规范的循环里，作为桥接的元素不能重复使用——不然要么是路径回头了，要么说明存在更小的循环嵌套。

我现在卡在了一个点：该用哪种图结构来表示这种关系？我试过把每个集合当作图的节点，标记集合之间的连接关系，但这显然不对——比如[{1,2},{1,3},{1,4}]，所有集合都通过共同元素1相连，但这里根本不存在循环。我也试过给每个集合里的每个数字单独分配一个标识，但这也行不通，因为没法区分集合内部的循环情况。

这个问题是源于一个关于生成唯一笛卡尔积的讨论。

举个具体的集合例子，这里面既有简单循环（比如4>17--17>4），也有更长的循环（比如13>5--5>11--11>13）：

[{1, 13, 5}, {11, 13}, {17, 11, 4, 5}, {17, 4, 1}]

另一种可视化类比 #

还有一种更直观的方式来理解这种“路径/循环”：把它想象成网格上的点连接——每一列对应一个集合，列中的点就是集合里的元素，相同的元素会被放在同一行。循环就是从某个点出发，通过垂直（跨行，也就是相同元素在不同集合间跳转）或水平（同列，也就是同一集合内的元素跳转）移动，最终回到起点的路径，而且路径必须同时包含两种方向的移动。如果调整行和列的排列顺序，这种循环会呈现出阶梯多边形的形状。

参考相关讨论 #

• 无向图中的简单环检测
• 无向图中的多边形检测

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