Tukukkk

I presently have a data table containing two columns - 'id' and 'prevId'. I would like to create a chain of ids by starting with a first row, finding a second row whose 'id' equals the first row's 'prevId', and repeating this process until 'prevId' is blank.

I would then like to identify the 'id' in the end of the chain without a 'prevId', and create a new column listing this originator 'id' for every row.

Below is an example of my desired output:

   id                  prevId originatorId createdAt

1: 11a                        11a          2018/1/12 

2: 11b                 11a    11a          2018/1/13

3: 11c                 11b    11a          2018/1/14

4: 12a                        12a          2018/1/12        

5: 12b                 12a    12a          2018/1/13

Any guidance would be appreciated, thanks!

Edit:

I have noticed a caveat while testing some of the proposed solutions. There may be instances where an element has a 'prevId' that is not seen as an 'id' in any other element. If I were to use to run chinsoon's solution:

DT[, originatorId:=id[1L], by=cumsum(prevId==“”)]

It would cause such elements to list the closest peer without a 'prevId' as its originator, even if that peer was not part of the id-prevId chain. An example:

   id                  prevId originatorId createdAt

1: 10a                        10a          2018/1/12 

2: 11b                 11a    10a          2018/1/13

3: 11c                 11b    10a          2018/1/14

In this instance, '11a' should be the originator for the 2nd and 3rd elements, but because it isn't present, '10a' gets the spot instead. Is there a tweak that could fix this? Much appreciated.

This is now recursive with two recursive steps, using dplyr and data.table functionality.

dt <- structure(list(id = c("11a", "11b", "11c", "12a", "12b"), prevId = c(NA,  "11a", "11b", NA, "12a")), row.names = c(NA, -5L), class = c("data.table", "data.frame"))



data.table(left_join(x = dt

       , y = dt[,.(prevId)]

       , by = c("id" = "prevId")) %>% left_join(

                                            y = dt[,.(id,prevId)]

                                            , by = c("prevId" = "id")

       ))[, .(id, prevId, originatorId = ifelse(is.na(prevId.y), ifelse(is.na(prevId), id, prevId), prevId.y ))]



>  id   prevId  originatorId

1: 11a   <NA>          11a

2: 11b    11a          11a

3: 11c    11b          11a

4: 12a   <NA>          12a

5: 12b    12a          12a

Expanded the example to incorporate the comment by @Michael. It is pretty scalable and allows to adjust the number of recursive steps, by adding additional joins into the pipe. It saves the resulting joined data.table after each iteration and thus allows to follow the matching steps pretty easily. Finally, the results of each join are combined and the resulting table should offer a good overview over the chain of ids in the data.

library(dplyr)

left_join(x = dt

          , y = dt[,.(prevId)]

          , by = c("id" = "prevId")) %>% data.table(.) %>% { . ->> dt.join.1}   %>% left_join(x = .

                                                                                 , y = dt[,.(Second.id = id, Second.prevId = prevId)]

                                                                                , by = c("prevId" = "Second.id")) %>%  data.table(.) %>% { . ->> dt.join.2}





dt.join.final.data <- rbindlist(list(  dt.join.1

                                       , dt.join.2)

                                , fill = TRUE

                                , idcol = "id"

                                , use.names = TRUE)

The resulting data.table looks then like this:

> dt.join.final.data

    id  id prevId Second.prevId

 1:  1 11a   <NA>          <NA>

 2:  1 11b    11a          <NA>

 3:  1 11c    11b          <NA>

 4:  1 12a   <NA>          <NA>

 5:  1 12b    12a          <NA>

 6:  2 11a   <NA>          <NA>

 7:  2 11b    11a          <NA>

 8:  2 11c    11b           11a

 9:  2 12a   <NA>          <NA>

10:  2 12b    12a          <NA>

I managed to solve this by defining a recursive function and applying it to all rows.

find_originatorId = function(current_row, df){

    if(current_row[["prevId"]] == ""){

        current_row[["id"]]

    } else {

        parent_row = df[df$id == current_row[["prevId"]],]

        find_originatorId(parent_row, df)

    }

}



df$originatorId = apply(df, 1, find_originatorId, df)