разбиение списка на отсортированные подсписки - PullRequest
Новая
       37

разбиение списка на отсортированные подсписки

0 голосов
/ 16 декабря 2018

Я пытаюсь разбить список с целыми числами на подсписки с возрастающими значениями.

в качестве примера: [1;2;3;3;4] должен перейти в [[1;2;3;3;4]] и список [1;2;3;2;4;3;5] -> [[1;2;3],[2;4],[3;5]].

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

Ответы [ 2 ]

0 голосов
/ 16 декабря 2018

Если вы покажете, что вы пробовали, то мы сможем помочь вам в том конкретном моменте, в котором вы застряли.

Также попробуйте обобщить вашу проблему, чтобы найти возможные подходы, которые имеютмне уже предлагали, например «У меня есть частично отсортированный список, и я хочу разделить его по предикату, сравнивая два смежных значения».Это, возможно, привело вас к существующим ответам, например, F # Как отобразить последовательность на основе предиката, а не фиксированной длины

Если они не соответствуют вашим требованиям, попробуйте этот,Это вложенная рекурсивная функция с аккумулятором и аргументом, объединенными в кортеж, где после использования всех аргументов аккумулятор и его подсписки нуждаются в обращении. 

let splitWhen p xs =
    let rec aux = function
    | ((y::_)::_) as yss, x::xs when p x y -> aux ([x]::yss, xs)
    | ys::yss, x::xs -> aux ((x::ys)::yss, xs)
    | [], x::xs -> aux ([[x]], xs)
    | yss, [] -> List.rev <| List.map List.rev yss
    aux ([], xs)

splitWhen (<) [1;2;3;3;4]
// val it : int list list = [[1; 2; 3; 3; 4]]
splitWhen (<) [1;2;3;2;4;3;5]
// val it : int list list = [[1; 2; 3]; [2; 4]; [3; 5]]

Редактировать

Хорошо, давайте сделаем шаг назад.Рекурсивная функция должна быть tail recursive , то есть вы не должны иметь незаконченного бизнеса при рекурсивном вызове функции;это может переполнить стек.Это, в свою очередь, требует дополнительного аргумента для накопления промежуточных значений, которые вы вычислили до сих пор, который обычно называется аккумулятором.

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

Легко увидеть, как тест предикатов можетбыть учтены, что приведет к версии выше. 

let rec splitList<'T when 'T: comparison> (acc : 'T list list) (list: 'T list) : 'T list list =
    match acc, list with
    | (y::_) as ys::yss, x::xs -> 
        if x >= y then splitList ((x::ys)::yss) xs
        else splitList ([x]::acc) xs
    | _, x::xs -> splitList [[x]] xs
    | _ -> List.rev (List.map List.rev acc)

splitList [] [1;2;3;3;4]
// val it : int list list = [[1; 2; 3; 3; 4]]
splitList [] [1;2;3;2;4;3;5]
// val it : int list list = [[1; 2; 3]; [2; 4]; [3; 5]]

Edit2

Вы также можете использовать не аккумулятор, а понимание списка (он же список выражение последовательности ) вместо этого.Это своего рода обман, так как для этого нужна вспомогательная функция, которая использует аккумулятор;он выдаст подпись val splitList : list:'a list -> 'a list list when 'a : comparison. 

let rec partitionWhile p = function
| x::xs, y::ys when p x y -> partitionWhile p (y::x::xs, ys)
| xss, yss -> List.rev xss, yss

let rec splitList list = [
    if not <| List.isEmpty list then
        let acc, rest = partitionWhile (<=) ([list.Head], list.Tail)
        if not <| List.isEmpty acc then
            yield acc
        yield! splitList rest ]

splitList [1;2;3;3;4]
// val it : int list list = [[1; 2; 3; 3; 4]]
splitList [1;2;3;2;4;3;5]
// val it : int list list = [[1; 2; 3]; [2; 4]; [3; 5]]
0 голосов
/ 16 декабря 2018

Вы можете использовать 2 аккумулятора. 

let  splitToSorted lst =
let rec loop lst sub acc = 
    match lst with
    | [] -> (sub |> List.rev)::acc |> List.rev
    | h::t -> match sub with
              | [] -> loop t [h] acc
              | x::xs -> if (x < h)
                         then loop t (h::sub) acc
                         else loop t [x] ((sub |> List.rev)::acc)
loop lst [] []
...