Разделить список на два равных списка в F #

Question

Я действительно новичок в F #, и мне нужно немного помочь с проблемой F #.

Мне нужно реализовать функцию обрезки, которая разбивает список пополам, чтобы вывод был ...

вырезать [1; 2; 3; 4; 5; 6] ;;

val it: int list * int list = ([1; 2; 3], [4; 5; 6])

Могу предположить, что длина списка четна.

Я также должен определить вспомогательную функцию gencut (n, xs), которая разрезает xs на две части, где n дает размер первой части:

gencut (2, [1; 3; 4; 2; 7; 0; 9]) ;;

val it: int list * int list = ([1; 3], [4; 2; 7; 0; 9])

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

Спасибо!

Answer 1

Поскольку ваш список имеет четную длину, а вы аккуратно его разрезаете пополам, я рекомендую следующее (сначала psuedocode):

• Начните с двух указателей: slow и fast.
• slow пошагово проходит по списку по одному элементу за раз, fast пошагово по двум элементам за раз.
• slow добавляет каждый элемент к переменной аккумулятора, тогда как fast движется вперед.
• Когда указатель fast достигает конца списка, указатель slow будет иметь только половину числа элементов, поэтому он находится в середине массива.
• Вернуть элементы slow перешагнул + оставшиеся элементы. Это должно быть два списка аккуратно пополам.

Процесс, описанный выше, требует одного обхода по списку и выполняется за время O (n).

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

let cut l =
    let rec cut = function
        | xs, ([] | [_]) -> xs
        | [], _ -> []
        | x::xs, y::y'::ys -> cut (xs, ys)
    cut (l, l)

Примечание x::xs шаг 1 элемент, y::y'::ys шаг два.

Эта функция возвращает вторую половину списка. Его очень легко изменить, поэтому он также возвращает первую половину списка.

Answer 2

Вы ищете нарезку списка в F #. @Juliet получил отличный ответ в этой теме: Функциональность, подобная фрагменту из списка в F #

В основном все сводится к тому, что это не встроено, поскольку в списках F # нет доступа к индексу с постоянным временем, но вы можете обойти это как подробно. Ее подход, примененный к вашей проблеме, даст (не очень эффективное, но работающее) решение:

let gencut(n, list) = 
    let firstList = list |> Seq.take n |> Seq.toList
    let secondList = list |> Seq.skip n |> Seq.toList
    (firstList, secondList)

Answer 3

У меня такая же домашняя работа, это было мое решение.Я просто студент и новичок в F #

let rec gencut(n, listb) = 
    let rec cut  n (lista : int list)  (listb : int list) =
        match (n , listb ) with
        | 0, _   ->  lista, listb
        | _, []  -> lista, listb
        | _, b :: listb -> cut  (n - 1) (List.rev (b :: lista ))  listb
    cut n [] listb

let cut xs = gencut((List.length xs) / 2, xs)  

Возможно, это не лучшее рекурсивное решение, но оно работает.Я думаю

Answer 4

Вот еще один способ сделать это, используя встроенные библиотечные функции, которые могут быть или не быть проще для понимания, чем некоторые другие ответы. Это решение также требует только одного обхода ввода. После того, как я посмотрел на вашу проблему, моей первой мыслью было то, что вы хотите что-то вроде List.partition, которая разбивает список на два списка на основе заданного предиката. Однако в вашем случае этот предикат будет основан на индексе текущего элемента, который раздел не может обработать, если не считать поиск индекса для каждого элемента.

Мы можем создать собственный эквивалент этого поведения, используя fold или foldBack. Здесь я буду использовать foldBack, так как это означает, что вам не нужно будет переворачивать списки позже (см. Отличный ответ Стивенса). То, что мы собираемся сделать здесь, это использовать складку, чтобы предоставить наш собственный индекс, а также два списка вывода, все в качестве аккумулятора. Вот общая функция, которая разделит ваш список на два списка на основе индекса n:

let gencut n input =
    //calculate the length of the list first so we can work out the index
    let inputLength = input |> List.length 
    let results =
        List.foldBack( fun elem acc-> 
                            let a,b,index = acc     //decompose accumulator
                            if (inputLength - index) <= n then (elem::a,b,index+1)
                            else (a,elem::b,index+1)  ) input ([],[],0)
    let a,b,c = results
    (a,b) //dump the index, leaving the two lists as output.

Итак, вы видите, что мы запускаем foldBack с начальным значением аккумулятора ([], [], 0). Однако, поскольку мы начинаем с конца списка, 0, представляющий текущий индекс, необходимо вычесть из общей длины списка, чтобы получить фактический индекс текущего элемента.

Затем мы просто проверяем, находится ли текущий индекс в диапазоне n. Если это так, мы обновляем аккумулятор, добавляя текущий элемент в список a, оставляя список b в покое, и увеличиваем индекс на 1: (elem :: a, b, index + 1). Во всех остальных случаях мы делаем то же самое, но вместо этого добавляем элемент в список b: (a, elem :: b, index + 1).

Теперь вы можете легко создать свою функцию, которая разделяет список пополам, создавая другую функцию, например:

let cut input = 
    let half = (input |> List.length) / 2
    input |> gencut half

Надеюсь, это может вам чем-то помочь!

> cut data;;
val it : int list * int list = ([1; 2; 3], [4; 5; 6])

> gencut 5 data;;
val it : int list * int list = ([1; 2; 3; 4; 5], [6])

РЕДАКТИРОВАТЬ: вы можете избежать отрицания индекса, указав длину в качестве начального значения аккумулятора и отрицая ее в каждом цикле, вместо того, чтобы увеличивать ее - возможно, проще так:)

let gencut n input =
    let results =
        List.foldBack( fun elem acc-> 
                            let a,b,index = acc     //decompose accumulator
                            if index <= n then (elem::a,b,index-1)
                            else (a,elem::b,index-1)  ) input ([],[],List.length input)
    let a,b,c = results
    (a,b) //dump the index, leaving the two lists as output.

Answer 5

(мне не понравился мой предыдущий ответ, поэтому я удалил его)

Первое, с чего начать при атаке на проблемы list, - это посмотреть на модуль List, который заполнен функциями высшего порядка, которые обобщают многие общие проблемы и могут дать вам краткие решения. Если вы не можете найти там ничего подходящего, то вы можете взглянуть на модуль Seq для таких решений, как продемонстрированный @BrokenGlass (но вы можете столкнуться там с проблемами производительности). Далее вы захотите рассмотреть рекурсию и сопоставление с образцом. Существует два вида рекурсии, которые вы должны учитывать при обработке списков: хвостовой и не хвостовой. Есть компромиссы. Хвосто-рекурсивные решения включают использование аккумулятора для передачи состояния, что позволяет вам разместить рекурсивный вызов в хвостовой позиции и избежать переполнения стека с большими списками. Но тогда вы, как правило, получите обратный список! Например,

Хвост-рекурсивный gencut Решение:

let gencutTailRecursive n input =
    let rec gencut cur acc = function
        | hd::tl when cur < n ->
            gencut (cur+1) (hd::acc) tl
        | rest -> (List.rev acc), rest //need to reverse accumulator!
    gencut 0 [] input

Нерекурсивное gencut решение:

let gencutNonTailRecursive n input =
    let rec gencut cur = function
        | hd::tl when cur < n ->
            let x, y = gencut (cur+1) tl //stackoverflow with big lists!
            hd::x, y
        | rest -> [], rest
    gencut 0 input

Если у вас есть решение gencut, его очень легко определить cut:

let cut input = gencut ((List.length input)/2) input

Answer 6

проверьте это:

let gencut s xs =  
    ([for i in 0 .. s - 1 -> List.nth xs i], [for i in s .. (List.length xs) - 1 -> List.nth xs i])

Вы просто звоните

let cut xs =                            
    gencut ((List.length xs) / 2) xs

с продолжительностью n и только одной итерацией, разделенной на две

Answer 7

Вы можете использовать List.nth для произвольного доступа и составления списков для генерации вспомогательной функции:

let Sublist x y data = [ for z in x..(y - 1) -> List.nth data z ]

Это вернет элементы [x..y] из данных. Используя это, вы можете легко генерировать функции gencut и cut (не забудьте проверить границы для x и y):)