сравнить два класса эквивалентности (продолжение)

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 -> ???

Это функция, которую я пытался выполнить в списке целых.но эта функция не была удовлетворена, она все еще отсутствует, чтобы проверить остальную часть списка.

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

Это совершенно неправильно, если вы пытаетесь создать топологическую сортировку ваших элементов. Вы говорите, что несопоставимые элементы равны, что является полной ерундой и приведет к путанице в алгоритме сортировки.

Если вы хотите иметь реальный топологический порядок, вы должны выполнить следующие шаги:

• построить входной список в виде списка, содержащего только одного представителя на класс; список вывода пуст
• до тех пор, пока список ввода не станет пустым:
  • выбрать случайный корень (без входного ребра) в списке ввода и удалить его из списка
  • добавить (в любом порядке) все элементы корневых представителей в выходной список
• вернуть список вывода

В зависимости от используемых вами структур данных этот алгоритм может быть более или менее эффективным, но ваш вопрос недостаточно точен, чтобы я мог рассказать вам больше.