如何用Haskell統計2D列表中給定元素周圍1的數量？

假設我有以下嵌套列表：如何用Haskell統計2D列表中給定元素周圍1的數量？

list = 
    [[0, 1, 0], 
    [1, 9, 1], 
    [1, 1, 0]]

假設你只給x和9. y座標我如何使用Haskell代碼，找出1的多少圍繞9號？

讓我再澄清一點，假設數字9位於（0,0）。我所試圖做的是這樣的：

int sum = 0; 
for(int i = -1; i <= 1; i++){ 
    for(int j = -1; j <= 1; j++){ 
    if(i == 0 || j == 0) continue; 
    sum += list[i][j]; 
    } 
}

周邊的位置（0,0）是下列座標：

 
(-1, -1) (0, -1) (1, -1) 
(-1, 0)   (1, 0) 
(-1, 1) (0, 1) (1, 1)

來源

2011-09-28 nobody

那麼你嘗試過和你在哪裏有問題？ – sth

這看起來非常像家庭作業問題。如果是，請添加「家庭作業」標籤。 –

定義'環繞'。對角線數量還是不對？這聽起來就像是一個摺疊的小摺疊，帶有一點小功能，可以檢查你是否離目標座標一個位置。 –

list = [[0,1,0],[1,9,1],[1,1,0]] 
s x y = sum [list !! j !! i | i <- [x-1..x+1], j <- [y-1..y+1], i /= x || j /= y] 
--s 1 1 --> 5

請注意，我沒有糾錯，如果座標位於邊緣。你可以通過添加更多條件來理解。

如果事情變得更大，列表列表並不是最有效的數據結構。你可以考慮向量，或者一個Map (Int,Int) Int（特別是如果你有很多可以被忽略的零）。

[編輯]

這裏有一個稍微更快的版本：

s x y xss = let snip i zs = take 3 $ drop (i-1) zs 
       sqr = map (snip x) $ snip y xss 
      in sum (concat sqr) - sqr !! 1 !! 1

首先，我們「喀嚓了」 3×3平方，那麼我們做這一切的計算。再次，邊緣上的座標將導致錯誤的結果。

來源

2011-09-28 08:38:24 Landei

我在所有的邊上加了0 – nobody

特別是，如果你使用隨機訪問方式，list的列表並不是最有效的數據結構''!!。當順序訪問時，它們不是無效的。但是你是對的，數組或地圖會表現得更好。 – leftaroundabout

@leftaroundabout：我不知道，在這種情況下，我認爲列表可以非常高效，如果您同時使用'zip'而不是'!!'來計算所有的總和（我們不需要隨機訪問，我們只是需要重新安排我們需要的）。 – rampion

編輯：切換到總結周圍8，而不是周圍的4

多久你只是想只是一個入口周圍的計數？如果你想要它所有的條目，列表仍然表現相當好，你只需要整體看它。

module Grid where 
import Data.List (zipWith4) 

-- given a grid A, generate grid B s.t. 
-- B(x,y) = A(x-1,y-1) + A(x,y-1) + A(x+1,y-1) 
--  + A(x-1,y)    + A(x+1,y) 
--  + A(x-1,y+1) + A(x,y+1) + A(x+1,y+1) 
-- (where undefined indexes are assumed to be 0) 
surrsum :: [[Int]] -> [[Int]] 
surrsum rs = zipWith3 merge rs ([] : init rs') (tail rs' ++ [[]]) 
    where -- calculate the 3 element sums on each row, so we can reuse them 
     rs'   = flip map rs $ \xs -> zipWith3 add3 xs (0 : xs) (tail xs ++ [0]) 
     add3 a b c  = a+b+c 
     add4 a b c d = a+b+c+d 
     merge [] _ _ = [] 
     -- add the left cell, right cell, and the 3-element sums above and below (zero-padded) 
     merge as bs cs = zipWith4 add4 (0 : init as) (tail as ++ [0]) (bs ++ repeat 0) (cs ++ repeat 0) 

-- given a grid A, replace entries not equal to 1 with 0 
onesOnly :: [[Int]] -> [[Int]] 
onesOnly = map . map $ \e -> if e == 1 then 1 else 0 

list :: [[Int]] 
list = [[0, 1, 0] 
     ,[1, 9, 1] 
     ,[1, 1, 0]]

現在你可以下降到ghci中看到它的工作：

*Grid Control.Monad> mapM_ (putStrLn . unwords . map show) list 
0 1 0 
1 9 1 
1 1 0 
*Grid Control.Monad> mapM_ (putStrLn . unwords . map show) $ onesOnly list 
0 1 0 
1 0 1 
1 1 0 
*Grid Control.Monad> mapM_ (putStrLn . unwords . map show) . surrsum $ onesOnly list 
2 2 2 
3 5 2 
2 3 2

來源

2011-09-28 14:43:11 rampion

如何用Haskell統計2D列表中給定元素周圍1的數量？

回答

相關問題