Проверка каждого значения в списке друг с другом - PullRequest
Новая
       12

Проверка каждого значения в списке друг с другом

3 голосов
/ 17 февраля 2012

Я работаю с OCaml, и у меня есть список, где мне нужно проверить все элементы в списке друг с другом.Список представляет собой список единиц, базовых или производных единиц.Базовыми единицами являются m, s, g, а производными единицами являются любые единицы, которые используют m, s, g, например, кг, мин, футы, фунты и т. Д.

Так что примерным списком будет [lb;футов;м].Этот список будет недействительным, потому что ft и m используют один и тот же базовый блок: m.Чтобы быть более ясным [фунт;кг;s] будет недействительным, потому что lb и kg используют одну и ту же базовую единицу: m.Однако [футов;s;м] полностью действителен.Эти преобразования базовых единиц хранятся в хэше для поиска.

Моя проблема в том, как я могу проверить все устройства друг с другом.Я пытался использовать складки, но у меня болит голова.Кто-нибудь может мне помочь?

Ответы [ 2 ]

2 голосов
/ 17 февраля 2012

Простое решение с квадратичной сложностью: 

(* [check_pair] should return [false] if check fails *)
let rec check_each_pair check_pair = function
  | [] -> true
  | hd1 :: rest ->
    let rec check_rest = function
      | [] -> true
      | hd2 :: rest -> check_pair hd1 hd2 && check_rest rest
    in
    check_rest rest && check_each_pair check_pair rest

Обратите внимание, что внутренний check_rest проверяет только предикат для каждого элемента списка. Это List.for_all. 

let rec check_each_pair check_pair = function
  | [] -> true
  | hd1 :: rest ->
    List.for_all (check_pair hd1) rest && check_each_pair check_pair rest

Вы можете сходить с ума от комбинатора, а также реализовывать check_each_pair как вызов комбинатора рекурсии, но это не является прямым (вам нужно как-то накапливать rest, так что сбросьте, но тогда вы хотите, чтобы ярлык был неудачным в начале семантика ...) и я не вижу никакого преимущества.

1 голос
/ 17 февраля 2012

Простое решение состоит в том, чтобы сначала создать список всех пар из списка (используя декартово произведение списка вместе с самим собой) и проверить условие в списке пар позже: 

let cartesian xs ys =
    List.concat (List.map (fun x -> List.map (fun y -> (x, y)) ys) xs)

let haveDifferentBases(x, x') =
   (* check whether they have different base units *)

let check_all_pairs xs =
   List.for_all haveDifferentBases (cartesian xs xs)
...