Объединение списков «пространственных» кортежей

Question

У меня есть три списка кортежей, каждый из которых содержит (startpos, endpos, value).

То, что я хочу сделать, это объединить их в один список кортежей (startpos, endpos, values ​​[]), но следуя правилу, которое мне проще нарисовать, чем написать:

//third               [---------]                    [------------]
//second        [-------------]              [---------------------------]
//first   [-----------------------------]    [--------------]
//(pos)   0123456789|123456789|123456789|123456789|123456789|123456789|123456789
//result  [--1-][--2-][---3---][---1----]    [---2--][---3--]

(Числа в результате представляют ожидаемую длину списка значений [] для каждого результирующего элемента)

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

Позиции можно рассматривать как имеющие тип int. Как видно из результата, сегменты «split» начинаются и заканчиваются не в одной и той же позиции, а в pos-1 или pos + 1. Порядок значений не важен, если он определен.

Пример данных (на основе приведенного выше примера):

let third =  [(12,22,3.1);(43,56,3.2)]
let second = [(6,20,2.1);(35,63,2.2)]
let first =  [(0,30,1.1);(35,50,1.2)]
let after =  [
                (0,5,[1.1]);
                (6,11,[1.1;2.1]);
                (12,20,[1.1;2.1;3.1]);
                (21,30,[1.1]);
                (35,42,[1.2;2.2]);
                (43,50,[1.2;2.2;3.2])
             ]

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

ОБНОВЛЕНИЕ На самом деле, если мы обобщили регистр ввода, чтобы он уже имел тип (int*int*List<float>), мы могли бы просто обработать регистр двух списков ввода, а затем сложить это.

PS: Это не домашняя работа или код-гольф, я просто несколько стерилизовал данные.

Answer 1

Ваши after данные неверны; по крайней мере, моя программа так думает, и я верю в это. :)

let third =  [(12,22,3.1);(43,56,3.2)] 
let second = [(6,20,2.1);(35,63,2.2)] 
let first =  [(0,30,1.1);(35,50,1.2)] 

let all = List.concat [first; second; third]
let min = all |> Seq.map (fun (x,y,z)->x) |> Seq.min 
let max = all |> Seq.map (fun (x,y,z)->y) |> Seq.max

let setsEachValueIsIn =
    [min..max] 
    |> List.map (fun i -> 
        i, all 
            |> List.filter (fun (x,y,z) -> x<=i && i<=y) 
            |> List.map (fun (x,y,z) -> z))

printfn "%A" setsEachValueIsIn

let x1,l1 = Seq.nth 0 setsEachValueIsIn

let result = 
    setsEachValueIsIn 
    |> List.fold (fun (((l,h,s)::t) as prev) (nx,ns) -> 
                    if s=ns then (l,nx,s)::t else (nx,nx,ns)::prev
                ) [x1,x1,l1]
    |> List.rev

let after =  [ 
                (0,5,[1.1]); 
                (6,11,[1.1;2.1]); 
                (12,20,[1.1;2.1;3.1]); 
                (21,30,[1.1]); 
                (35,42,[1.2;2.2]); 
                (43,50,[1.2;2.2;3.2]) 
             ] 

printfn ""
printfn "%A" result
printfn ""
printfn "%A" after
assert(result = after)

Стратегия: сначала я сопоставляю каждое число во всем диапазоне с «наборами, в которых оно находится». Затем я сбрасываю, высевая с первым результатом как (min,min,setsMinIsIn), и на каждом этапе пути, если набор не меняется, я просто расширяю диапазон, иначе, если набор меняется, я создаю новый элемент.

Ключ для имен переменных в сгибе: l ow, h igh, s et, nx -следующий x, ns -следующий набор

Answer 2

Полная перезапись (см. Правки), более короткая, более элегантная, возможно, менее читаемая. Все еще сжимаю логику Брайана.

ОБНОВЛЕНИЕ : теперь работает, по крайней мере, для теста выше

let third =  [(12,22,3.1);(43,56,3.2)]
let second = [(6,20,2.1);(35,63,2.2)]
let first =  [(0,30,1.1);(35,50,1.2)]

//===helper functions===
// foldable combined min and max finder
let minmax (mn,mx) (x,y,_) = (min mn x, max mx y)  
// test if x - y range overlaps position i
let overlaps i (x,y,_) = x<=i && i<=y 
// get third element from triple
let getz (_,_,z) = z              

//specialise function, given two tuples, will combine lists (L & U)
//  but only if both lists have contents AND their indexes (il & iu) 
//  are not more than 1 apart, i is included simply so that we can pass 
//  merge directly to the List.map2 below
let merge (i,il,L) (_,iu,U) = 
     if L = [] || U = [] || iu - il > 1 then 
        (i, il, L) 
     else  
        (i, iu, L @ U)

let input = [first;second;third] // input data - 'bottom' first
//find max and min positions
let (x0,yn) = input |> Seq.concat |> Seq.fold minmax (0,0) 

//transform each data list to a list of (i,[z])
let valsByPos = input |> List.map (fun level -> //for each data 'level' 
                [x0..yn] |> List.map (fun i ->   //for each position in range
                     //collect values of all elements in level that
                     // overlap this position
                     (i, level |> List.filter (overlaps i) |> List.map getz)))

// 'merge up' each level, keeping only upper values if lower values exist
// after we will have just one list of (i, [z])
let mergedValsByPos = valsByPos //offside here for SO formatting
          //add an index into each tuple
          |> List.mapi (fun i l -> l |> List.map (fun (j,z) -> (j,i,z)))  
          //use index to determine if we should 'merge up' for each subsublst
          |> List.reduce (List.map2 merge) 
          //rip the index back out                     
          |> List.map (fun (i,_,z) -> (i,z)) 

//get first value as seed for fold
let x1,l1 = Seq.nth 0 mergedValsByPos

//transform list (i,[z]) into list of (x,y,[z])
//key: (l)ow, (h)igh, (s)et, (nx)-next x, (ns)-next set
let result = 
    mergedValsByPos 
    //first remove any positions where there are no values
    |> List.filter (fun el -> snd(el) <> [])
    //double capture on state so we can take all or part of it
    |> List.fold (fun (((l,h,s)::t) as prev) (nx,ns) -> 
                    //if [z] value hasn't changed, we just enlarge range
                    //  of current state (from (l,h) to (l,nx)) 
                    //  otherwise we add a new element (nx,nx,ns) to state
                    if s=ns then (l,nx,s)::t else (nx,nx,ns)::prev 
                ) [x1,x1,l1] //initial state from seed values
    |> List.rev //folded value is backwards (because of::), so reverse