比较两个等价类（续）

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，这种算法可以或多或少的效率，但你的问题是不够的准确地告诉你更多。