比較兩個等價類（續）

Question

val compare : bool array array -> 'a list -> 'a list -> int 

比較m在列表中生成字典順序。我不知道怎麼填???

let rec compare m c c' = 
    match c with 
    | [] -> (match c' with 
      | [] -> 0 
      | _ :: _ -> -1) 
    | hd1 :: tl1 -> (match c' with 
        | [] -> 1 
        | hd2 :: tl2 -> ??? 

這是我嘗試在INTS的名單做一個功能。但是這個函數並不滿足，它仍然缺少檢查列表的其餘部分。

let cmp_classes m c c' = 
    match c, c' with 
    | i :: _, j :: _ -> 
     begin 
     match m.(i).(j), m.(j).(i) with 
     (* same class: there is a path between i and j, and between j and i *) 
      | true, true -> 0 
     (* there is a path between i and j *) 
      | true, false -> 1 
     (* there is a path between j and i *) 
      | false, true -> -1 
     (* i and j are not compareable *) 
      | false, false -> 0 
     end 
    | _ -> assert false 

你能幫我嗎？因爲當我嘗試使用此功能在int

let cmp_classes m i j = 
    match m.(i).(j), m.(j).(i) with 
     (* same class: there is a path between i and j, and between j and i *) 
      | true, true -> 0 
     (* there is a path between i and j *) 
      | true, false -> 1 
     (* there is a path between j and i *) 
      | false, true -> -1 
     (* i and j are not compareable *) 
      | false, false -> 0 

它仍然沒有返回數據我測試正確的順序。 我一直在做這個功能很多次，當我不得不一次又一次地嘗試，但沒有發現什麼是錯誤的時候，它真的被卡住了。拜託我需要你的幫忙。謝謝

Answer 1

(* i and j are not compareable *) 
     | false, false -> 0 

如果您試圖對您的元素進行拓撲排序，這是完全錯誤的。你說的是無可比擬的元素是相等的，這是完全廢話，會混淆排序算法。

如果你想有一個真正的拓撲順序應遵循以下步驟：

• 建立一個輸入列表中含有每類僅一個representant列表;輸出列表爲空
• 直到輸入列表爲空：
  • 選取一個隨機根（沒有輸入邊緣）在輸入列表，並從列表中刪除它
  • 追加（以任何次序）的所有元素在輸出列表
• 回報輸出列表

根據您所使用的數據結構的根representants，這種算法可以或多或少的效率，但你的問題是不夠的準確地告訴你更多。