在Haskell中求矩阵的所有对角线

8gsdolmq  于 2022-11-14  发布在  其他
关注(0)|答案(5)|浏览(211)

二维列表如下所示:
或在纯粹的 haskell

[ [1,2,3], [4,5,6], [7,8,9] ]

diagonals [ [1,2,3], [4,5,6], [7,8,9] ]的预期输出为

[ [1], [4, 2], [7, 5, 3], [8, 6], [9] ]

allDiagonals(包括反对角线)是很简单的:

allDiagonals :: [[a]] -> [[a]]
allDiagonals xss = (diagonals xss) ++ (diagonals (rotate90 xss))

我对这个问题的研究

StackOverflow也有类似的问题

  • Python这个问题是关于Python中的同一个问题,但是Python和Haskell是非常不同的,所以这个问题的答案与我无关。
  • Only one这个问题和答案是在 haskell ,但只是关于中心对角线。

"胡格尔"
搜索[[a]] -> [[a]]没有得到任何有趣的结果。
独立思考**
我认为索引遵循一种以x为基数的计数,其中x是矩阵中的维数,请看:
对角线是[ [1], [3, 2], [4] ]

  • 可以在matrix[0][0]中找到1
  • 可以在matrix[1][0]中找到3
  • 可以在matrix[0][1]中找到2
  • 可以在matrix[1][1]中找到1

这类似于以2为基数计算3,也就是矩阵大小减1,但这太模糊了,无法转换成代码。

ekqde3dh

ekqde3dh1#

universe-base-1.0.2.1开始,您可以简单地调用diagonals函数:

Data.Universe.Helpers> diagonals [ [1,2,3], [4,5,6], [7,8,9] ]
[[1],[4,2],[7,5,3],[8,6],[9]]

完整的实作如下所示:

diagonals :: [[a]] -> [[a]]
diagonals = tail . go [] where
    -- it is critical for some applications that we start producing answers
    -- before inspecting es_
    go b es_ = [h | h:_ <- b] : case es_ of
        []   -> transpose ts
        e:es -> go (e:ts) es
        where ts = [t | _:t <- b]

关键的想法是我们保留两个列表:一个矩形块,我们还没有开始检查,还有一个五边形块(一个左上角的三角形被切掉的矩形!)。对于五边形块,从每个列表中选出第一个元素会给我们另一条对角线。然后,我们可以从矩形块中添加一个新的行,未检查的块在我们删除对角线后剩下的地方。
这个实现看起来可能有点不自然,但它的设计是非常高效和懒惰的:我们要做的唯一一件事就是把列表分解成头和尾,所以矩阵中元素的总数应该是O(n);并且我们在完成反结构化后立即生成元素,所以垃圾回收是非常懒惰/友好的。它也适用于无限大的矩阵。
(我为您推出此版本:以前最接近的方法是使用diagonal,它只会给予[1,4,2,7,5,3,8,6,9],而没有您想要的额外结构。)

z0qdvdin

z0qdvdin2#

下面是一个递归版本,假设输入总是格式良好的:

diagonals []       = []
diagonals ([]:xss) = xss
diagonals xss      = zipWith (++) (map ((:[]) . head) xss ++ repeat [])
                                  ([]:(diagonals (map tail xss)))

它是递归的,从一列到另一列。一列的值与从减少一列的矩阵中得到的对角线组合,然后移动一行,得到对角线。希望这个解释有意义。
举例说明:

diagonals [[1,2,3],[4,5,6],[7,8,9]]
= zipWith (++) [[1],[4],[7],[],[],...] [[],[2],[5,3],[8,6],[9]]
= [[1],[4,2],[7,5,3],[8,6],[9]]

另一个版本是针对行而不是列,但基于相同的思想:

diagonals []       = repeat []
diagonals (xs:xss) = takeWhile (not . null) $
    zipWith (++) (map (:[]) xs ++ repeat [])
                 ([]:diagonals xss)

与指定的结果相比,结果的对角线是相反的。当然,这可以通过应用map reverse来修复。

oknrviil

oknrviil3#

import Data.List

rotate90 = reverse . transpose
rotate180 = rotate90 . rotate90

diagonals = (++) <$> transpose . zipWith drop [0..]
                 <*> transpose . zipWith drop [1..] . rotate180

它首先得到主对角线([1,5,9])和上对角线([2,6][3]);然后是下面的对角线:[8,4][7]中的一个或多个。
如果您关心顺序(即您认为应该说[4,8]而不是[8,4]),请在最后一行插入map reverse .

ewm0tg9j

ewm0tg9j4#

一个又一个方案:

diagonals = map concat
          . transpose
          . zipWith (\ns xs -> ns ++ map (:[]) xs)
                    (iterate ([]:) [])

基本上,我们把

[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

进入

[[1], [2], [3]]
[[] , [4], [5], [6]]
[[] , [] , [7], [8], [9]]

然后是transposeconcat列表。对角线的顺序相反。
但这不是很有效率,也不适用于无限列表。

yv5phkfx

yv5phkfx5#

这里有一种方法:

f :: [[a]] -> [[a]]
f vals = 
    let n = length vals
    in [[(vals !! y) !! x | x <- [0..(n - 1)], 
                            y <- [0..(n - 1)], 
                            x + y == k] 
        | k <- [0 .. 2*(n-1)]]

例如,在GHCi中使用它:

Prelude> let f vals = [ [(vals !! y) !! x | x <- [0..(length vals) - 1], y <- [0..(length vals) - 1], x + y == k] | k <- [0 .. 2*((length vals) - 1)]]

Prelude> f [ [1,2,3], [4,5,6], [7,8,9] ]
[[1],[4,2],[7,5,3],[8,6],[9]]

假设一个正方形n x n矩阵,将有n + n - 1条对角线(这是k所迭代的)并且对于每个对角线,不变量是行和列索引之和为对角线值(从左上角的零索引开始)。您可以交换项目访问顺序(将!! y !! x交换为!! x !! y),以反转矩阵上的光栅扫描顺序。

相关问题