使用多重索引查找与特定模式匹配的所有组合

Question

我需要编写一个算法，需要 N 个点，并输出由这些点形成的所有可能的 3 星形和三角形。这是一个澄清的例子。

让N = 4，那么我有4个选择2 = 6个距离，集合

{(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}

我们将三星级定义为共享 1 个索引的 3 个距离。例如

{(0,1),(1,2),(1,3)}

是一颗星星，但

{(0,1),(1,2),(2,3)}

不是。三角形定义为三个距离，其中第一对和第二对、第二对和第三对、第三对和第一对共享一个索引，例如

{(0,1),(1,2),(0,2)}

，但不是

{(0,1),(1,2),(1,3)}

。

我需要取 N 并输出所有此类 3 星和所有三角形的列表。它们可以位于相同的列表中，也可以位于不同的输出列表中。

有没有快速的方法来做到这一点？我正在使用 python，因此可以访问 pandas 多重索引，我认为这可能有用。

到目前为止，我已经尝试使用一种非常简单的方法，我只是通过 1 到 NC2 循环 6 个变量，并使用指示符函数来挑选所有三角形。我还成功地使用多索引选出了 3 星级：

edges = list(itertools.combinations(range(N),2))
mi = pd.MultiIndex.from_tuples(edges)

# all 3 pairs share 1 index
for i in range(c):
    core = mi[i]
    arr = np.bitwise_xor(mi.get_level_values(0) == core[0], mi.get_level_values(1) == core[1])
    for (outer1, outer2) in itertools.combinations(mi[arr], 2):
        if outer1[0] in outer2 or outer1[1] in outer2:
            print(core, outer1, outer2)

但这会复制每颗星星。

我确信有一个简单的方法可以做到这一点，但我似乎无法理解它，所以任何帮助将不胜感激。谢谢

Answer 1

我们先来看看星星。由于我们有一个完整的图，以顶点 0 为中心点的星的数量是从顶点开始的大小为 3 的组合的数量！= 0，或者

combinations(range(1,N), 3)

星形从中心点到其他三个顶点都有一条边。

以顶点1为中心点的星体数量是相同的，但是我们已经统计了包含0和1的星体数量，所以我们应该只统计索引大于1的顶点组合，导致

combinations(range(2,N), 3)

推广顶点

i

，这给出

combinations(range(i+1,N), 3)

请注意，如果我们希望起始顶点能够连接到索引大于其自身的三个其他顶点，则起始顶点最多可以是

N-3

。

from itertools import combinations

N = 5
for i in range(N-3):
    for (v1, v2, v3) in combinations(range(i+1,N), 3):
        L = list({(i, v1), (i, v2), (i, v3)})
        print(L)

这会导致：

[(0, 1), (0, 2), (0, 3)]
[(0, 1), (0, 2), (0, 4)]
[(0, 1), (0, 3), (0, 4)]
[(0, 2), (0, 3), (0, 4)]
[(1, 2), (1, 3), (1, 4)]

同样，对于三角形，我们只需选择两个顶点（索引大于起始索引，以避免重复）并构造适当的边：

for i in range(N-2):
    for (v2, v3) in combinations(range(i+1,N), 2):
        L = list({(i, v2), (v2, v3), (v3, i)})
        print(L)

结果：

[(0, 1), (1, 2), (2, 0)]
[(0, 1), (1, 3), (3, 0)]
[(0, 1), (4, 0), (1, 4)]
[(2, 3), (0, 2), (3, 0)]
[(0, 2), (4, 0), (2, 4)]
[(4, 0), (0, 3), (3, 4)]
[(2, 3), (1, 2), (3, 1)]
[(2, 4), (1, 2), (4, 1)]
[(1, 3), (3, 4), (4, 1)]
[(2, 3), (3, 4), (4, 2)]