Сгруппируйте последовательность в сегменты на основе сравнения дискретных ключей с границами интервалов. - PullRequest
Новая
       12

Сгруппируйте последовательность в сегменты на основе сравнения дискретных ключей с границами интервалов.

0 голосов
/ 24 апреля 2020

На днях на этот вопрос типа домашнего задания ( Создать список нестандартного типа в F # и создать две последовательности этого списка ) можно было бы легко ответить, поскольку возможны только два исхода (подумайте *) 1003 *). Меня удивило, как обобщить группирование в сегменты, включая или исключая соответствующие граничные значения.

При заданном входном значении [5; 10; 15; 45; 50; 55] и границах интервалов [10; 20; 50] получим две группировки 

[[5; 10]; [15]; [45; 50]; [55]] // less-than-and-equal
[[5]; [10; 15]; [45]; [50; 55]] // greater-than-and-equal

Я, наверное, обдумываю это. 

type 'a ComparisonResult = Under of 'a | Over of 'a

let internal splitter op standardResult extraResultValue boundaries keySelector arg =
    boundaries |> List.tryFind (op (keySelector arg)) |> function
    | None -> extraResultValue
    | Some x -> standardResult x

let under boundaries =  // under and including
    boundaries |> List.rev |> splitter (>) Over (boundaries |> List.head |> Under)

let over boundaries =   // over and including
    boundaries |> splitter (<) Under (boundaries |> List.rev |> List.head |> Over)

[5; 10; 15; 45; 50; 55]
|> Seq.groupBy (under [10; 20; 50] id)
|> printfn "%A"

[5; 10; 15; 45; 50; 55]
|> Seq.groupBy (over [10; 20; 50] id)
|> printfn "%A"

Ответы [ 2 ]

2 голосов
/ 24 апреля 2020

Вот мое решение. Я думаю, что это не очень хорошо для многих границ. 

let chunkByInterval predicate boundaries list =
    list
    |> List.groupBy (fun x -> boundaries |> List.countBy (fun b -> predicate x b))
    |> List.map snd

chunkByInterval (<=) [10; 20; 50] [5; 10; 15; 45; 50; 55] 
// [[5; 10]; [15]; [45; 50]; [55]]

chunkByInterval (>=) [10; 20; 50] [5; 10; 15; 45; 50; 55] 
// [[5]; [10; 15]; [45]; [50; 55]]
1 голос
/ 24 апреля 2020

Вот хвосто-рекурсивное решение, проходящее вместе оба списка и накапливающее «чанк». 

let chunkByInterval list intervals compare = 
    let rec chunk list intervals acc = 
        match (acc, list, intervals) with
        | (head::tail), (x::xs as xs'), (y::ys as ys') ->  
            if compare x y then 
                chunk xs ys' ((x::head)::tail) 
            else 
                chunk xs' ys ([]::acc)
        | (_, xs, _) -> xs::acc

    chunk list intervals [[]] |> List.filter (not << List.isEmpty) |> List.map List.rev |> List.rev

И использование: 

chunkByInterval [5; 10; 15; 45; 50; 55] [10; 20; 50] (<=) //[[5; 10]; [15]; [45; 50]; [55]]

Небольшой недостаток что, поскольку мы накапливаем минусы, мы должны полностью изменить список в конце. Это также предполагает, что оба списка отсортированы, но зачастую быстрее сначала отсортировать их, чем выполнять поиск O (n ^ 2) или использовать поиск.

Для этого существует элегантное решение с выражениями последовательности та же проблема - определенно проще с пакетом Interactive Extensions.

...