从图中生成所有三元组？

Question

我想从图中生成所有三元组。第一个“集合”中的所有三元组将是 1,2,3 和 1,3,2 和 3,2,1。我对这组的另一个三元组（即 2,1,3 或 3,1,2 ）不感兴趣。我怎样才能做到这一点？

Answer 1

正如对该问题的评论中所讨论的那样，目前还不清楚墓志铭的具体设置是什么，出于某种原因，他/她似乎不愿意澄清。但是让我们假设“图形”实际上只是由一个距离矩阵表示（这可能是问题中数字和 X 的混乱应该显示的内容），每对顶点都有一个实际的数字距离。

在那种情况下，这里没有什么非常图形化的东西；每对顶点无一例外都有一条边；我们所能做的就是枚举每个顶点的三元组。

对于每一组的三个顶点A，B，C，我们需要检查d（A，B）<= d（A，C）+ d（C，B），并且d（A，C）<= d（ a,b)+d(b,c)，并且 d(b,c) <= d(b,a)+d(a,c)。所以让我们这样做。以下是伪代码，因为如果我尝试用 PHP（我尽可能少使用）编写它，我会出错。

for i from 0 to n_vertices-3
  for j from i+1 to n_vertices-2
    for k from j+1 to n_vertices-1
      # now i,j,k are three distinct vertices, and every set of three vertices
      # will occur once as we run through the loops.
      a = distances[i,j]
      b = distances[i,k]
      c = distances[j,k]
      if a>b+c or b>a+c or c>a+b
        triangle inequality is violated; complain

如果您的图形以距离矩阵以外的其他方式表示，或者如果许多边可能不存在，那么您需要做一些不同的事情。

（注意：如果你的图应该满足三角不等式，那么可以说它不应该缺少任何边，除非它实际上是断开的。这取决于距离是否旨在“从 x 到 y 的整体最短距离”（在在这种情况下，如果三角不等式失败，那么某些东西就被破坏了，并且连接图中不应该有不存在的边）或“从 x 到 y 的直接路径的距离”（在这种情况下，如果三角不等式失败，则仅表明所谓的直接路径不值得使用）。