2

Я ищу самый лучший вариант как написать программу в OCaml, которая перемешает элементы списка по следующим способу.

Первое число мы вынимаем из списка, и от других мы сделаем два списка, чтобы числа на четных позициях шли в левый список если будут меньше чем первое, и в правый список если будут большее. Числа на нечетных позициях наоборот пойдут налево если будут больше и направо если будут меньше...

Пример: [6; 4; 8; 2; 3; 10; 7; 9] ---> ([4; 8; 2; 7]) 6 ([3; 10; 9])

Спасибо большое за ответы!

4
  • что за счетные позиции?
    – Grundy
    9 дек 2016 в 8:41
  • я думаю, что имеются ввиду четные и нечетные позиции :)
    – ivg
    9 дек 2016 в 12:02
  • @ivg, да, похоже на то.
    – Grundy
    9 дек 2016 в 12:08
  • @Grundy Да, точно так, извините!
    – Майкл
    9 дек 2016 в 12:14

2 ответа 2

1

Ниже представлено решение с использованием стандартной функции fold_left, что позволяет явно не использовать рекурсию. Используется по сути тот же подход, что был использован @ivg, однако, здесь на каждом шаге инвертируется булева переменная (even_pos, принимающая истинные значения на чётных позициях) вместо инвертирования порядка аргументов у оператора <. Основная логика сосредоточена в функции f.

let partition = function
  | [] -> ([], [])
  | first :: xs ->
     let f (even_pos, (ys, zs)) x =
       let lists =
         if (even_pos && x < first) || (not even_pos && x > first)
           then (x :: ys, zs)
           else (ys, x :: zs)
       in (not even_pos, lists)
     in List.fold_left f (true, ([], [])) xs |> snd

Примечание 1: в исходном задании не очень понятно что делать в случае, если очередной элемент списка равен голове списка. Это вне зависимости от чётности позиции, т.к. у сравнения три возможных результата: больше / меньше / равно. При уточнении задания решение нетрудно будет доработать.

Примечание 2: порядок элементов в выходных списках обращён.

Примечание 3: голова списка имеет номер 1 (т.е. эта позиция нечётна).

1

При реализации этой функции мы можем воспользоваться двумя замечательными свойствами:

  1. за четным числом идет нечетное, а за нечетным четное
  2. по условию задачи, знак сравнения инвертируется на каждом шагу

Эти замечательные свойства позволяют нам отказаться от того чтобы хранить счетчик позиции и проверять его на четность. Мы начинаем с четной позиции и на каждом шаге рекурсии мы просто поворачиваем знак сравнения в обратную сторону. Для этого мы используем функцию flip:

let flip f x y = f y x

Таким образом flip (<) даёт нам (>), а flip (flip (<)) даёт обратно (<). (Тут есть маленькая проблема с эффективностью, но об этом позже).

Далее мы можем реализовать функцию в точности с её словесным определением (даже проще):

let partition xs =
  let rec loop b cmp ls rs = function
    | [] -> ls,rs
    | x :: xs ->
      let ls,rs = if cmp x b then x::ls,rs else ls,x::rs in
      loop b (flip cmp) ls rs xs in
  match xs with
  | [] -> [],[]
  | x :: xs -> loop x (<) [] [] xs

На каждом шаге мы сравниваем, используя текущую функцию сравнения, значение из списка с опорным значением, и кладем его либо в левый список ls, либо в правый rs, затем мы применяем тот же алгоритм к оставшимся элементам, но инвертируем нашу функцию сравнения. Когда мы дошли до конца, мы возвращаем нашу пару накопленных списков. Мы можем их инвертировать, если хочется иметь значения в том же порядке, в котором они шли в оригинальном списке. Так как в условиях это не уговорено, я решил не инвертировать.

Наша реализация получилась достаточно эффективной, за одним маленьким исключением, выражение flip cmp каждый раз создаёт новую функцию, которая содержит ссылку на cmp. Если применить flip N раз, то мы будем иметь цепочку функций длиной N, которая в итоге приведет нас к функции (<). И хотя нам кажется весьма очевидным, что flip (flip f) равно f доказаться это для компилятора не так просто, для этого ему нужно знать теорию функций, и ещё иметь возможность доказать, что flip не имеет никаких побочных эффектов. Новые версии компилятора, во многих случаях, способны это определить, но не в таком сложном рекурсивном случае.

Таким образом, если нас сильно заботит производительность (и мы доказали, что этот кусок кода действительно является бутылочным горлышком), то мы должны переписать flip, используя знание того, что мы имеем всего две функции: < и > и то что flip < эквивалентно >. Реализацию более эффективной версии, я оставляю читателю, в качестве увлекательного домашнего задания.

1
  • Красивая идея с flip! 9 дек 2016 в 19:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.