那些遇到过的问题

如何在R中找到图上所有可能的有效路径？

ken*_*e17 1 performance r combinatorics igraph tidygraph

我正在 R 中解决一个有趣的问题（可能使用igraph和/或tidygraph库），我需要在图表上找到满足某些条件的所有可能路径。问题可以简化为：

我有16 个不同的节点，可以分为4组，每个节点都有一个特征，称之为颜色。*注意：以下可能不是表示数据的最佳方式，但希望它能传达情况。

nodes_set_1 <- c("red", "blue", "orange")
nodes_set_2 <- c("green", "blue", "red", "yellow", "purple")
nodes_set_3 <- c("blue", "green", "red", "orange", "purple")
nodes_set_4 <- c("orange", "blue", "green")
Run Code Online (Sandbox Code Playgroud)

我现在需要找到这些节点之间满足以下三个条件的所有可能路径： (1) 每条路径必须恰好包含每组中的一个节点。(2) 图形是从nodes_set_1到nodes_set_2到nodes_set_3到nodes_set_4 (3) 单个路径中颜色不能重复。

例如，以下路径是有效的：

path_1 <- c(nodes_set_1[1], nodes_set_2[1], nodes_set_3[1], nodes_set_4[1])

下面的路径将无效，因为颜色“蓝色”重复：

path_2 <- c(nodes_set_1[2], nodes_set_2[2], nodes_set_3[2], nodes_set_4[2])

我希望得到一些关于设置和解决这个问题的建议。找到一种有效确定是否不存在有效解决方案的方法也将令人惊奇。

谢谢你！

Tho*_*ing 5

基础 R 选项

我不认为你真的需要igraph或tidygraph找到所有可能的路径，并且基本 R 应该足以实现它。下面有两个选项：

- expand.grid+Filter

用于expand.grid生成所有组合，然后根据标准对其进行子集化

nodes_lst <- list(nodes_set_1, nodes_set_2, nodes_set_3, nodes_set_4)
ps <- Filter(Negate(anyDuplicated), asplit(unname(expand.grid(nodes_lst)), 1))
Run Code Online (Sandbox Code Playgroud)

你会看到

> ps
[[1]]
[1] "red"    "green"  "blue"   "orange"

[[2]]
[1] "red"    "yellow" "blue"   "orange"

[[3]]
[1] "red"    "purple" "blue"   "orange"

[[4]]
[1] "red"    "blue"   "green"  "orange"

[[5]]
[1] "blue"   "red"    "green"  "orange"

[[6]]
[1] "red"    "yellow" "green"  "orange"

[[7]]
[1] "blue"   "yellow" "green"  "orange"

[[8]]
[1] "red"    "purple" "green"  "orange"

[[9]]
[1] "blue"   "purple" "green"  "orange"

[[10]]
[1] "blue"   "green"  "red"    "orange"

[[11]]
[1] "blue"   "yellow" "red"    "orange"

[[12]]
[1] "blue"   "purple" "red"    "orange"

[[13]]
[1] "red"    "green"  "purple" "orange"

[[14]]
[1] "blue"   "green"  "purple" "orange"

[[15]]
[1] "red"    "blue"   "purple" "orange"

[[16]]
[1] "blue"   "red"    "purple" "orange"

[[17]]
[1] "red"    "yellow" "purple" "orange"

[[18]]
[1] "blue"   "yellow" "purple" "orange"

[[19]]
[1] "orange" "red"    "green"  "blue"  

[[20]]
[1] "red"    "yellow" "green"  "blue"

[[21]]
[1] "orange" "yellow" "green"  "blue"

[[22]]
[1] "red"    "purple" "green"  "blue"

[[23]]
[1] "orange" "purple" "green"  "blue"

[[24]]
[1] "orange" "green"  "red"    "blue"

[[25]]
[1] "orange" "yellow" "red"    "blue"

[[26]]
[1] "orange" "purple" "red"    "blue"

[[27]]
[1] "red"    "green"  "orange" "blue"

[[28]]
[1] "red"    "yellow" "orange" "blue"

[[29]]
[1] "red"    "purple" "orange" "blue"

[[30]]
[1] "red"    "green"  "purple" "blue"

[[31]]
[1] "orange" "green"  "purple" "blue"

[[32]]
[1] "orange" "red"    "purple" "blue"

[[33]]
[1] "red"    "yellow" "purple" "blue"

[[34]]
[1] "orange" "yellow" "purple" "blue"

[[35]]
[1] "orange" "red"    "blue"   "green"

[[36]]
[1] "red"    "yellow" "blue"   "green"

[[37]]
[1] "orange" "yellow" "blue"   "green"

[[38]]
[1] "red"    "purple" "blue"   "green"

[[39]]
[1] "orange" "purple" "blue"   "green"

[[40]]
[1] "orange" "blue"   "red"    "green"

[[41]]
[1] "blue"   "yellow" "red"    "green"

[[42]]
[1] "orange" "yellow" "red"    "green"

[[43]]
[1] "blue"   "purple" "red"    "green"

[[44]]
[1] "orange" "purple" "red"    "green"

[[45]]
[1] "red"    "blue"   "orange" "green" 

[[46]]
[1] "blue"   "red"    "orange" "green"

[[47]]
[1] "red"    "yellow" "orange" "green"

[[48]]
[1] "blue"   "yellow" "orange" "green"

[[49]]
[1] "red"    "purple" "orange" "green"

[[50]]
[1] "blue"   "purple" "orange" "green"

[[51]]
[1] "red"    "blue"   "purple" "green"

[[52]]
[1] "orange" "blue"   "purple" "green"

[[53]]
[1] "blue"   "red"    "purple" "green"

[[54]]
[1] "orange" "red"    "purple" "green"

[[55]]
[1] "red"    "yellow" "purple" "green" 

[[56]]
[1] "blue"   "yellow" "purple" "green"

[[57]]
[1] "orange" "yellow" "purple" "green"
Run Code Online (Sandbox Code Playgroud)

- 递归（更高效）

可能更有效的方法是使用递归，通过定义自定义函数，以便在生成路径的过程中跳过所有可能的重复项

nodes_lst <- list(nodes_set_1, nodes_set_2, nodes_set_3, nodes_set_4)

f <- function(k = length(nodes_lst)) {
    if (k == 1) {
        return(as.list(nodes_lst[[k]]))
    }
    p <- nodes_lst[[k]]
    unlist(
        lapply(
            Recall(k - 1),
            \(x) Map(`c`, list(x), p[!p %in% x])
        ),
        recursive = FALSE
    )
}
Run Code Online (Sandbox Code Playgroud)

你可以简单地运行f()并获得

> f()
[[1]]
[1] "red"    "green"  "blue"   "orange"

[[2]]
[1] "red"    "green"  "orange" "blue"

[[3]]
[1] "red"    "green"  "purple" "orange"

[[4]]
[1] "red"    "green"  "purple" "blue"

[[5]]
[1] "red"    "blue"   "green"  "orange"

[[6]]
[1] "red"    "blue"   "orange" "green"

[[7]]
[1] "red"    "blue"   "purple" "orange"

[[8]]
[1] "red"    "blue"   "purple" "green"

[[9]]
[1] "red"    "yellow" "blue"   "orange"

[[10]]
[1] "red"    "yellow" "blue"   "green"

[[11]]
[1] "red"    "yellow" "green"  "orange"

[[12]]
[1] "red"    "yellow" "green"  "blue"

[[13]]
[1] "red"    "yellow" "orange" "blue"

[[14]]
[1] "red"    "yellow" "orange" "green"

[[15]]
[1] "red"    "yellow" "purple" "orange"

[[16]]
[1] "red"    "yellow" "purple" "blue"

[[17]]
[1] "red"    "yellow" "purple" "green"

[[18]]
[1] "red"    "purple" "blue"   "orange"

[[19]]
[1] "red"    "purple" "blue"   "green"

[[20]]
[1] "red"    "purple" "green"  "orange"

[[21]]
[1] "red"    "purple" "green"  "blue"

[[22]]
[1] "red"    "purple" "orange" "blue"

[[23]]
[1] "red"    "purple" "orange" "green"

[[24]]
[1] "blue"   "green"  "red"    "orange"

[[25]]
[1] "blue"   "green"  "purple" "orange"

[[26]]
[1] "blue"   "red"    "green"  "orange"

[[27]]
[1] "blue"   "red"    "orange" "green"

[[28]]
[1] "blue"   "red"    "purple" "orange"

[[29]]
[1] "blue"   "red"    "purple" "green"

[[30]]
[1] "blue"   "yellow" "green"  "orange"

[[31]]
[1] "blue"   "yellow" "red"    "orange"

[[32]]
[1] "blue"   "yellow" "red"    "green"

[[33]]
[1] "blue"   "yellow" "orange" "green"

[[34]]
[1] "blue"   "yellow" "purple" "orange"

[[35]]
[1] "blue"   "yellow" "purple" "green"

[[36]]
[1] "blue"   "purple" "green"  "orange"

[[37]]
[1] "blue"   "purple" "red"    "orange"

[[38]]
[1] "blue"   "purple" "red"    "green"

[[39]]
[1] "blue"   "purple" "orange" "green"

[[40]]
[1] "orange" "green"  "red"    "blue"

[[41]]
[1] "orange" "green"  "purple" "blue"

[[42]]
[1] "orange" "blue"   "red"    "green"

[[43]]
[1] "orange" "blue"   "purple" "green"

[[44]]
[1] "orange" "red"    "blue"   "green" 

[[45]]
[1] "orange" "red"    "green"  "blue"

[[46]]
[1] "orange" "red"    "purple" "blue"

[[47]]
[1] "orange" "red"    "purple" "green"

[[48]]
[1] "orange" "yellow" "blue"   "green"

[[49]]
[1] "orange" "yellow" "green"  "blue"

[[50]]
[1] "orange" "yellow" "red"    "blue"

[[51]]
[1] "orange" "yellow" "red"    "green"

[[52]]
[1] "orange" "yellow" "purple" "blue"

[[53]]
[1] "orange" "yellow" "purple" "green"

[[54]]
[1] "orange" "purple" "blue"   "green"

[[55]]
[1] "orange" "purple" "green"  "blue"

[[56]]
[1] "orange" "purple" "red"    "blue"

[[57]]
[1] "orange" "purple" "red"    "green"
Run Code Online (Sandbox Code Playgroud)

基准

microbenchmark(
    grid = Filter(Negate(anyDuplicated), asplit(unname(expand.grid(nodes_lst)), 1)),
    recur = f(),
    unit = "relative"
)
Run Code Online (Sandbox Code Playgroud)

节目

Unit: relative
  expr      min       lq     mean   median       uq      max neval
  grid 4.203662 4.403358 4.503495 4.518175 4.241935 7.159534   100
 recur 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000   100
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

201 次

最近记录：

1 年，9 月 前
相关归档
从OFFSET/FETCH NEXT获取总行数 79
R中的行名和列名 50
如何使用R重命名文件？ 39
R使用什么类型的正交多项式？ 25
r random forest error - 新数据中预测变量的类型不匹配 24
如何从列表列表中提取元素 19
x64与x86有如此不同的性能结果的原因是什么？ 15
fp:精确与fp:严格的表现 14
Java中的System.out.println()vs \n 8
C#的常见操作成本？ 7
难疑归档
AngularJS:服务与提供商vs工厂 3296
PHP:从数组中删除元素 2362
JavaScript对象的长度 2224
夏令时和时区最佳实践 2021
一次捕获多个异常？ 2015
如何按字典值对字典列表进行排序？ 1722
在C#中调用基础构造函数 1398
JavaScript中是否有"null coalescing"运算符？ 1305
如何在Ruby中将字符串转换为小写或大写 1081
在JavaScript中将Unix时间戳转换为时间 1054