檢查座標是否創建一個循環

我將一個沃克x/y座標的元組存儲在一個數組中ArrayBuffet((Int, Int))。檢查座標是否創建一個循環

步驟代表(0,0)和(2,1)之間的旅程可以((0,0), (0,1), (1,1), (2,1))，((0,0), (1,1), (2,1))等

麻煩的是，我需要一種方法來測試，如果步行者在圓圈旅行。

E.g.考慮從(0,0)到(0,1)，步行者的路徑是((0,0), (1,0), (1,-1), (0,0), (0,1))。步行者會繞着一圈走。

方法

def hasLoop(path: ArrayBuffer[(Int,Int)]): Boolean = { 
    if (path.length < 3) return false 
    else { 
     for i <- 0 to path.length - 1 { 
     val temp = path 
     temp.remove(i) 
     if (temp.contains(i)) return true 
     } 
     return false 
    } 
    }

如果沃克訪問在一個單一的旅程座標不止一次。然而，如果步行者從(0,0)到(0,1)或甚至到(0,2)，但然後通過(0,1)返回相同的路徑，那麼它不應該被看作循環。

任何人都可以爲我的isLoop方法提供解決方案嗎？

來源

2016-11-21 Duzzz

你的循環的定義是不明確的 - 如果我理解正確的話，一個路徑具有循環當且僅當它包含相同的_vertex_（例如'（0,0）'）多於一次，但存在多於一個路徑（由_edges_組成（例如'（0,0） - >（0,1） '）通過這個頂點？ –

如果我的理解正確，你只是想確定一個集合是否具有相同的值2次或更多次。

@annotation.tailrec 
def hasLoop(path: Seq[(Int, Int)]): Boolean = 
    if (path.size < 2) false 
    else if (path.tail.contains(path.head)) true 
    else hasLoop(path.tail) 

println(hasLoop(Array((0, 0), (0, 1)))) 
println(hasLoop(Array((0, 0), (1, 0), (1, -1), (0, 0), (0, 1))))

來源

2016-11-21 15:55:13 longshorej

如果我正確理解OP，方法應該返回false，例如'Array（（0,0），（1,0），（0,0））'（那只是「返回相同的方式「），爲此你的解決方案返回true。 –

很確定這個w由於你爲列表的每個元素做O（n）'contains'，所以在時間上很複雜。 – Daenyth

不知道它是最完美的解決方案，但我認爲它你需要什麼：

// some type aliases to make this more readable, can do without them too 
type Vertex = (Int,Int) 
type Edge = (Vertex, Vertex) 

def hasLoop(path: Array[Vertex]): Boolean = { 
    // create all edges - connections between one vertex and the next one in path 
    val edges: Array[Edge] = path.zip(path.drop(1)) 

    // fold right searching for PREVIOUS edges for which SRC equals current edge's DESTINATION, 
    // but DESTINATION does not equal current edge's SOURCE 
    val foldResult: (Seq[Edge], Boolean) = edges.foldLeft((Seq[Edge](), false)) { 
    case ((visited, found), e) => 
     (visited :+ e, found || visited.exists(oldE => oldE._1 == e._2 && oldE._2 != e._1)) 
    } 

    foldResult._2 // return the boolean result 
} 

println(hasLoop(Array((0,0), (1,0), (1,-1), (0,0), (0,1)))) // true 
println(hasLoop(Array((0,0), (1,0), (1,-1), (0,0)))) // true 
println(hasLoop(Array((0,0), (1,0), (1,-1), (1,0), (0,0)))) // false 
println(hasLoop(Array((0,0), (1,0), (1,-1)))) // false

來源

2016-11-21 16:18:31

檢查座標是否創建一個循環

回答

相關問題