Niedrigste Paar sequentielle Kombination Datentabelle

Question

Ich habe ein Set mit zwei Spalten. Die Zeilen sind Wertepaare (a, b).

require(data.table)   
dt<-data.table(a=c(1,11,11,2,7,5,6), b = c(2,9,8,6,5,3,3)) 

Ich möchte jedem Wertpaar die niedrigste Nummer zuweisen. Wenn jedoch einer der Werte erneut in einer neuen Zeile erscheint, muss er erneut mit dem neuen Paar verglichen und der niedrigste der Historie ausgewählt werden. Das Ergebnis muss diese:

res.dt<-data.table(a=c(1,11,11,2,7,5,6), b = c(2,9,8,6,5,3,3), res=c(1,9,8,1,5,3,1))   

    a b res 
1: 1 2 1 
2: 11 9 9 
3: 11 8 8 
4: 2 6 1 
5: 7 5 5 
6: 5 3 3 
7: 6 3 1 

Answer 1

das Problem anders angeben: Für jede Zeile i, müssen wir iterativ < = i in Reihen j res mit dem kleinsten Wert aktualisieren wo (a_i , b_i) und (a_j, b_j) haben einen nicht leeren Schnittpunkt.

Wir können dies tun, effizient mit non-equi joins in data.table (v> = 1.9.8), aber da diese Funktion nur Einzelelement Vergleiche erlaubt (>, >=, ==, <= oder <), müssen wir Kreuzungen finden durch getrenntes Vergleichen von (a_i, a_j), (a_i, b_j), (b_i, a_j), (b_i, b_j). (Es gibt einen Schnittpunkt, wenn zumindest eines dieser Paare identische Elemente enthält.) Auf diese iterativ für die gesamte Geschichte ausmacht, und wir können stoppen, wenn das Ergebnis konvergiert:

dt[, `:=`(idx=.I, res=pmin(a,b), prev_res=NA)] 

while (dt[, !identical(res, prev_res)]) { 
    dt[, prev_res:= res] 

    # Use non-equi joins to update 'res' for intersecting pairs downstream 
    dt[dt[, .(i.a=a, i.res=res, i=.I)], on=.(a==i.a, idx > i), res:= pmin(res, i.res)] 

    dt[dt[, .(i.a=a, i.res=res, i=.I)], on=.(b==i.a, idx > i), res:= pmin(res, i.res)] 

    dt[dt[, .(i.b=b, i.res=res, i=.I)], on=.(a==i.b, idx > i), res:= pmin(res, i.res)] 

    dt[dt[, .(i.b=b, i.res=res, i=.I)], on=.(b==i.b, idx > i), res:= pmin(res, i.res)] 

} 

Das Ergebnis:

> dt[, .(a,b,res)] 
#  a b res 
# 1: 1 2 1 
# 2: 11 9 9 
# 3: 11 8 8 
# 4: 2 6 1 
# 5: 7 5 5 
# 6: 5 3 3 
# 7: 6 3 1