r - 使用 dplyr 对随机交易列表进行排序

Question

假设有以下一组原始交易:

library(tidyverse)

original_transactions <- data.frame(
  row = 1:6,
  start = 0,
  change = runif(6, min = -10, max = 10) %>% round(2),
  end = 0
) %>% mutate(
  temp = cumsum(change),
  end = 100 + temp, # End balance
  start = end - change # Start balance
) %>% select(
  -temp
)

它显示了一个(按时间顺序)交易序列，起始余额为 100.00 美元，期末余额为 95.65 美元，有六次交易/更改。

现在假设你收到了一个困惑的版本

transactions <- original_transactions %>% sample_n(
  6
) %>% mutate(
  row = row_number() # Original sequence is unknown
)

如何对 R 中的序列进行逆向工程？即获取transactions的排序顺序匹配 original_transactions ?理想情况下，我想使用 dplyr 来执行此操作和一系列管道 %>%并避免循环。

假设开始/结束余额将是唯一的，并且一般而言，交易数量可能会有所不同。

Answer 1

首先，让

original_transactions
#   row  start change    end
# 1   1 100.00   2.33 102.33
# 2   2 102.33  -6.52  95.81
# 3   3  95.81  -4.20  91.61
# 4   4  91.61  -3.56  88.05
# 5   5  88.05   7.92  95.97
# 6   6  95.97   3.61  99.58

transactions
#   row  start change    end
# 1   1 100.00   2.33 102.33
# 2   2  91.61  -3.56  88.05
# 3   3  95.81  -4.20  91.61
# 4   4 102.33  -6.52  95.81
# 5   5  88.05   7.92  95.97
# 6   6  95.97   3.61  99.58

和

diffs <- outer(transactions$start, transactions$start, `-`)
matches <- abs(sweep(diffs, 2, transactions$change, `-`)) < 1e-3

我猜是计算 diffs是整个解决方案中计算成本最高的部分。 diffs有 start 之间所有可能的差异您的 transactions .然后将它们与 change 进行比较栏目matches我们知道 transactions 的哪几对行应该一起去如果数字精度没有问题，我们可以使用 match功能并快速完成。然而，在这种情况下，我们有以下 两个选项 .

首先，我们可以使用 igraph .

library(igraph)
(g <- graph_from_adjacency_matrix(t(matches) * 1))
# IGRAPH 45d33f0 D--- 6 5 -- 
# + edges from 45d33f0:
# [1] 1->4 2->5 3->2 4->3 5->6

也就是说，我们有一个隐藏路径图:1->4->3->2->5->6，我们想要恢复它。它由没有传入边的顶点的最长路径给出(即 1 ):

transactions[as.vector(tail(all_simple_paths(g, from = which(rowSums(matches) == 0)), 1)[[1]]), ]
#   row  start change    end
# 1   1 100.00   2.33 102.33
# 4   4 102.33  -6.52  95.81
# 3   3  95.81  -4.20  91.61
# 2   2  91.61  -3.56  88.05
# 5   5  88.05   7.92  95.97
# 6   6  95.97   3.61  99.58

另一种选择是递归。

fun <- function(x, path = x) {
  if(length(xNew <- which(matches[, x])) > 0)
    fun(xNew, c(path, xNew))
  else path
}
transactions[fun(which(rowSums(matches) == 0)), ]
#   row  start change    end
# 1   1 100.00   2.33 102.33
# 4   4 102.33  -6.52  95.81
# 3   3  95.81  -4.20  91.61
# 2   2  91.61  -3.56  88.05
# 5   5  88.05   7.92  95.97
# 6   6  95.97   3.61  99.58

它使用与前一种方法相同的唯一最长路径图思想。

没有显式循环......当然你可以用 %>% 重写所有内容。 ，但它不会像你想要的那么漂亮；这不是真正的传统数据转换任务，其中 dplyr是最好的。