haskell - 在图中找到三角形

Question

我有一个这样的图表:

作为家庭作业的一部分，我想找到三角形(1->2->5)。我不知道如何找到这个。

就我而言，我定义了我的图表:

type Graph = (Int, Int -> Int -> Bool)

g 2 3 = True
g 3 2 = True
g 1 2 = True
g 2 1 = True
g 1 1 = True
g n m = False

回答 2 条评论。

我这样做了，我认为它有效。

triangles :: [(Int, Int, Int)]
triangles = [(x, y, z) | x <- [1..3], y <- [1..x], z <- [1..y], isTriangle (x, y, z)]

isTriangle :: (Int, Int, Int) -> Bool
isTriangle  (x, y, z) = g x y && g y z && g x z

我删除了 (_,g) 和 (n,g) (我不明白为什么我们需要它们:)我调用triangles，它返回(1,1,1) (2,1,1)(在我的例子中)。是吗？

Answer 1

我猜 Graph 的第一个 Int 是您的节点的界限(例如，如果节点位于 [1..6] 中，则为 6)。

因此，您需要一个返回图形三角形的函数，因此类型可能是:

triangles :: Graph -> [(Int, Int, Int)]

现在，只要有 3 个节点，例如x，就存在三角形。 y和z ，所有组合返回 True通过g .

因此，您可能需要考虑生成所有这些组合(可能避免通过重新排序而等效的组合)，并仅过滤掉那些验证条件的组合:

isTriangle :: Graph -> (Int, Int, Int) -> Bool
isTriangle (_, g) (x, y, z) == g x y && g y z && g x z

为此，您可以使用list comprehension ，或函数 filter其类型为 (a -> Bool) -> [a] -> [a]

<小时/>

回答您的第一条评论:

首先，您需要实现 triangles函数，这就是错误的原因。但是，正如您在 test 中所做的那样，您可以简单地即时生成这些三角形。

现在，你写道:

test = filter (isTriangle) [(x,y,z) | x <- [1..3], y <- [1..3], z <- [1..3]]

关于此的两件事:

• 首先，您不需要 isTriangle 两边的括号对于你写的内容，但它是不正确的，因为 isTriangle期望图形作为其第一个参数

• 其次，您将获得大量重复项，如果您愿意，您可以通过首先不生成它们来防止这种情况:

  test = filter (isTriangle) [(x,y,z) | x <- [1..3], y <- [1..x], z <- [1..y]]
  

或者，您可以忽略 filter通过在列表理解语法中提供保护来实现功能，如下所示:

[(x, y, z) | x <- [1..3],  y <- [1..x], z <- [1..y], isTriangle yourGraph (x, y, z)]

现在，我将让您继续了解细节。您需要将其设为一个带有图形的函数，并替换此 3图中的节点数，yourGraph 图中的节点数。

既然您选择使用列表理解，请忘记我之前写的生成函数，它的目的只是为 filter 生成输入。 ，但是使用列表理解方法，您不一定需要它。

<小时/>

回答您的第二条评论:

你想写一个函数:

triangles :: Graph -> [(Int, Int, Int)]
triangles (n, g) = [(x, y, z) | ...]

...将被替换为之前的正确内容(x、y 和 z 的范围，以及谓词 isTriangle)。

或者，您可以将其分为两个函数:

allTriangles :: Int -> [(Int, Int, Int)]
allTriangles n = [(x, y, z) | ...]

graphTriangles :: Graph -> [(Int, Int, Int)]
graphTriangles (n, g) = [t | t <- allTriangles n, isGraphTriangle t]
    where isGraphTriangle (x, y, z) = ...

这样，您就可以重复使用 allTriangles为了别的事。如果觉得没必要，可以继续一击大领悟triangles ，因为这是一项作业，您可能不会在其基础上进行构建。

我尽量不填写所有...这样你就可以自己做并希望理解:)

<小时/>

更正您的解决方案:

首先，我在范围上的错误，应该是 x <- [1..n], y <- [x+1..n], z <- [y+1..n]哪里n表示图中的节点数。这样，您只捕获三元组，其中 x < y < z ，这确保您只能看到每组三个点出现一次。

其次，我将图表作为函数的参数的原因是您可能希望为另一个图表重用相同的函数。通过硬编码g和6在您的函数中，您可以使它们真正特定于您所描述的特定图形，但如果您想计算 triangles在一定数量的图表上，您不想为每个图表编写一个函数!