查找列表中的3对构成循环参考的集合

Question

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

我有一个通过索引确定的参考点列表。这些索引值是线的起点和终点。 [EG Line 1 [1,3] Line2 [4,5]等

我试图在Pure 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)