尋找依賴關係的遞歸函數

我有一個地圖集合。鑑於任何地圖，我想找到它依賴的所有地圖。任何地圖都會有直接的依賴關係。每個直接依賴關係都會有自己的依賴關係，等等。尋找依賴關係的遞歸函數

我無法編寫遞歸函數。下面的代碼給出了一個stackoverflow錯誤。（無論如何這個算法效率不高 - 我希望能幫忙清理它）。

下面是我的實現 -

find-deps需要一個地圖，並返回地圖的科爾：在地圖的直接依賴關係。

（找到-DEPS [M]）=> COLL

的下面功能 -

檢查是否direct-deps，即時DEPS，是空的，作爲鹼的條件。
如果不是，它會在所有直接的折扣上映射find-deps。這是導致問題的步驟。

通常在遞歸函數中，我們能夠縮小初始輸入的範圍，但是在這裏我的輸入不斷增加！

(defn find-all-deps 
    ([m] 
    (find-all-deps m [])) 
    ([m all-deps] 
    (let [direct-deps (find-deps m)] 
     (if-not (seq direct-deps) 
     all-deps 
     (map #(find-all-deps % (concat all-deps %)) direct-deps)))))

來源

2014-12-24 murtaza52

有沒有可能你有一個依賴循環？ – fjarri

請舉例說明輸入失敗。 –

您的示例代碼不完整，find-deps函數未定義。 – arrdem

當使用有向圖時，通常有用的做法是確保不會兩次訪問圖中的節點。這個問題看起來很像很多圖形遍歷問題，並且你的解決方案非常接近正常的深度優先遍歷，你只需要不循環（或者不允許它們在輸入中）。開始的一種方法是在再次訪問之前確保依賴關係不在圖中。不幸的是map很不適合這個，因爲你映射的列表中的每個元素都無法知道同一列表中其他元素的依賴關係。 reduce在這裏更合適，因爲您正在尋找單一的答案。

... 
(if-not (seq direct-deps) 
    all-deps 
    (reduce (fn [result this-dep] 
       (if-not (contains? result this-dep) 
       (find-all-deps this-dep (conj result this-dep)) 
       result) 
      direct-deps 
      #{}) ;; use a set to prevent duplicates.

來源

2015-01-06 01:58:35

尋找依賴關係的遞歸函數

回答

相關問題