当前位置：文江博客话题详情

从图表生成所有三元组？

发布于 2024-10-31 07:43:45 字数 98 浏览 5 评论 0原文

我想从图中生成所有三元组。第一个“集合”中的所有三元组都是 1,2,3 和 1,3,2 和 3,2,1。我对此组的其他三元组（即 2,1,3 或 3,1,2 ）不感兴趣。我该怎么做？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

债姬 2024-11-07 07:43:45

正如该问题的评论中所讨论的，目前还不清楚墓志铭的设置是什么，并且出于某种原因，他/她似乎不愿意澄清。但我们假设“图”实际上只是由一个距离矩阵（这可能是问题中的数字和 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（我尽可能少使用 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 的直接路径的距离”（在这种情况下，如果三角不等式失败，它仅仅表明据称存在直接路径不值得使用）。）

As discussed in the comments to the question, it's not very clear exactly what epitaph's setup is, and for some reason s/he seems unwilling to clarify. But let's suppose that the "graph" is actually simply represented by a distance matrix (which may possibly be what the mess of numbers and Xs in the question is supposed to show), with an actual numeric distance for each pair of vertices.

In that case, there's nothing very graph-ish going on here; there's an edge for every pair of vertices without exception; and all we can do is to enumerate every single triple of vertices.

For each set of three vertices a,b,c we need to check that d(a,b) <= d(a,c)+d(c,b), and that d(a,c) <= d(a,b)+d(b,c), and that d(b,c) <= d(b,a)+d(a,c). So let's do that. The following is pseudocode because if I try to write it in PHP (which I use as seldom as possible) I'll make mistakes.

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

If your graph is represented in some way other than as a distance matrix, or if lots of edges might fail to exist, then you'd want to do something different.

(Note: if your graph is supposed to satisfy the triangle inequality, then arguably it shouldn't be missing any edges unless it's actually disconnected. It depends on whether the distances are intended to be "overall shortest distance from x to y" (in which case if the triangle inequality fails then something is broken, and there should be no absent edges in a connected graph) or "distance of direct path from x to y" (in which case if the triangle inequality fails it merely indicates that an allegedly direct path isn't worth using).)

回复收藏 0 原文

~没有更多了~