python - 在列表中查找形成循环引用的 3 对集合

Question

希望这是一个非常简单的问题，但我一直在为此烦恼。

我有一个通过索引标识的引用点列表。这些索引值是线的起点和终点。 EG 线路 1 [1,3] 线路 2 [4,5] 等

我尝试在纯 Python 中执行以下操作，并且已经运行了如此多的代码迭代，我无法再正常思考了。我确信这是某种列表管理解决方案......

**List 1:**

[1,3]
[4,5]
[2,1]
[5,1]
[3,2]
[4,1]

从列表 1 中我希望得到以下输出。

**List2**
[1,3]
[2,1]
[3,2]

**List3**
[4,5]
[5,1]
[4,1]

因此，结果是一组数据，它们有效地在它们之间提供了圆形/三角形关联。

请帮忙，我完全被难住了!

编辑: 我附上了我正在使用的数据结构的草图。您可以看到每条线都有一个起点和终点引用。识别列表中相应的“组”以便能够提取 3 个唯一的引用，这样我就可以生成一个三角形。

Link to Data Structure Example and Desired Output

迄今为止，我已经放弃了大部分代码，但尝试使用组合(我不想使用此方法，因为会有大量数据需要迭代)

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

input = IN[0]
result = []

for i in input:
    matrix = []
    matrix.append(combinations(i,3))
    result.append(matrix)

OUT = result

Answer 1

这样的事情怎么样？我们基本上只是检查每对相邻的顶点，看看它们是否有任何共同的邻居，如果有，那么就形成了一个三角形。我们对点 ( x < y < z ) 任意执行一些排序，这样我们就不会多次找到相同的三角形。

# given some input:
pairs = ([
[1,3],
[4,5],
[2,1],
[5,1],
[3,2],
[4,1]
])

# compute the set of neighbors of each vertex
from collections import defaultdict
neighbors = defaultdict(set)
for x, y in pairs:
  # enforce some arbitrary ordering x < y < z so that
  # we don't find the same triangle more than once
  if x < y:
    neighbors[x].add(y)
  else:
    neighbors[y].add(x)

# for each pair of adjacent neighbors
for (x, y) in pairs:
  # Optional sorting
  if x > y:
    (y, x) = (x, y)

  # (x, y, z) form a triangle if z is a common neighbor of x and y
  common_neighbors = neighbors[x] & neighbors[y]
  for z in common_neighbors:
    print((x,y,z))

生成三角形集合(与您提到的格式不完全相同，但应该具有相同的信息内容，请随意根据您的要求进行相应调整):

(1, 2, 3)
(1, 4, 5)