r - 在 R 中查找具有约束的值组合
问题描述
我在向量中有一组值,例如
all_points <- c(1, 4, 2, 12, 6, 5, 25)
我想找到所有可能的组合,其中从左到右的数字按升序排列。第一个和最后一个数字将始终包括在内。例如,在这种情况下,它们将是:
1, 4, 12, 25
1, 4, 6, 25
1, 4, 25
1, 2, 12, 25
1, 2, 6, 25
1, 2, 5, 25
1, 2, 25
1, 12, 25
1, 6, 25
1, 5, 25
1, 25
目前,我正在尝试实现一个递归函数来测试所有向右值的大小,并返回一个向量列表,但它不起作用。下面包括用于解释我的方法的部分 R 代码和部分伪代码。
my_recursive_function <- function(input_points, running_vector = c(1)){
start_point <- input_points[1]
rightward_points <- input_points[2:length(input_points)
for(i in 1:length(rightward_points)){
if(rightward_points[i] != 25 & rightward_points[i] > start_point){
set_of_points <- c(running_vector, rightward_points[i])
my_recursive_function(rightward_points, set_of_points)
}
if(rightward_points[i] == 25){
print(c(running_vector, 25)
flush.console()
#I will end up doing more than printing here, but this is enough for the example
}
#do something to return to the previous level of recursion,
#including returning running_vector and rightward_points
#to the appropriate states
}
所以希望这是有道理的。我有两个问题:
- 我是否过于复杂了,还有更好的方法吗?这是一种搜索算法,遍历树形结构,所以我可以在这里做一些我看不到的聪明的事情。
- 如果这是最好的方法,我该如何做底部的伪代码位?我很困惑试图弄清楚每个向量在每个递归级别中的样子,以及如何从我的 running_vector 中弹出元素。
解决方案
一种可能的方法是使用combn
不同的长度来创建所有可能的组合,如下所示:
combis <- lapply(0L:(length(all_points)-2L),
function(n) combn(
seq_along(all_points)[c(-1L, -length(all_points))],
n,
function(x) all_points[x],
FALSE))
lapply(unlist(combis, recursive=FALSE),
function(x) c(all_points[1L], x, all_points[length(all_points)]))
解释
1) 第一行代码获取n
第一个和最后一个元素之间的元素数 ( ) 并生成所有可能的索引组合,然后使用提取相应的元素function(x) all_points[x]
2)unlist(..., recursive=FALSE)
将列表取消嵌套 1 级。
3)lapply(..., function(x) c(sorted[1L], x, sorted[length(sorted)]))
将第一个和最后一个元素附加到每个组合
输出
[[1]]
[1] 1 25
[[2]]
[1] 1 4 25
[[3]]
[1] 1 2 25
[[4]]
[1] 1 12 25
[[5]]
[1] 1 6 25
[[6]]
[1] 1 5 25
[[7]]
[1] 1 4 2 25
[[8]]
[1] 1 4 12 25
[[9]]
[1] 1 4 6 25
[[10]]
[1] 1 4 5 25
[[11]]
[1] 1 2 12 25
[[12]]
[1] 1 2 6 25
[[13]]
[1] 1 2 5 25
[[14]]
[1] 1 12 6 25
[[15]]
[1] 1 12 5 25
[[16]]
[1] 1 6 5 25
[[17]]
[1] 1 4 2 12 25
[[18]]
[1] 1 4 2 6 25
[[19]]
[1] 1 4 2 5 25
[[20]]
[1] 1 4 12 6 25
[[21]]
[1] 1 4 12 5 25
[[22]]
[1] 1 4 6 5 25
[[23]]
[1] 1 2 12 6 25
[[24]]
[1] 1 2 12 5 25
[[25]]
[1] 1 2 6 5 25
[[26]]
[1] 1 12 6 5 25
[[27]]
[1] 1 4 2 12 6 25
[[28]]
[1] 1 4 2 12 5 25
[[29]]
[1] 1 4 2 6 5 25
[[30]]
[1] 1 4 12 6 5 25
[[31]]
[1] 1 2 12 6 5 25
[[32]]
[1] 1 4 2 12 6 5 25
推荐阅读
- python - 如何解决 Gensim 无法使用 pattern3 的问题?
- python - Python脚本将数据从txt提取到csv
- android - Android Navigation - 手动设置导航图后无法更改工具栏标题
- apache-spark - 如何在 AWS EMR 中完全停止/杀死 spark 结构化流作业?
- javascript - Javascript 没有改变 HTML 背景图片
- verilog - 如何在 Verilog 设计中正确编写这个 for 循环条件?
- vb.net - 窗口资源管理器打开时冻结
- java - Flutter 如何将java代码添加到flutter模块
- javascript - 使用 Fetch API 时的“结果”是什么?
- reactjs - Ant Design - 如何在 antd 中将表格包装到 Form.List 中