合併「空間」元組列表

Question

我有三個元組列表，每個元組包含（startpos，endpos，value）。

我想要做的就是這些合併成元組的一個列表（startpos，endpos，值[]），但以下我覺得它更容易吸引比寫一個規則：

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

（結果中的數字表示每個結果元素的值[]列表的預期長度）

基本上，我只保留一個「更高」的元素，它與「下」元素重疊，並且我分成了「同質「元素。

該職位可以被認爲是類型int。正如你從結果中可以看到的那樣，'分割'部分不會在相同的位置開始和結束，而是在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]) 
      ] 

現在，我發現它思考這個問題的功能性的方式很難，任何想到的是勢在必行。也許這就是在這種情況下必然的，但如果任何人有任何想法...

UPDATE其實，如果我們廣義的輸入情況下已經是類型（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)，並且每一步，如果該集合沒有改變，我只是擴大範圍，否則如果集合確實改變了，我做一個新的元素。

主要用於在摺疊VAR名稱：l流，h室內運動場，s等，nx - 下X，ns - 下設置

Answer 2

完全重寫（見編輯），短，更優雅，也許更少可讀性。仍然捏Brian的邏輯。

UPDATE：現在的作品，至少在上述試驗

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