在 R 中查找值与约束的组合

Question

我在向量中有一组值，例如

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

目前，我正在尝试实现一个递归函数来测试所有向右值的大小，以及 returns 一个向量列表，但它不起作用。下面包括部分 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
    }

所以希望这是有道理的。我有 2 个问题：

我是不是太复杂了，还有更好的方法吗？这是一种搜索算法，遍历树结构，所以我可以在这里做一些我看不到的聪明的事情。
如果这是最好的方法，我该怎么做底部的伪代码位？我是试图弄清楚每个向量的外观时变得非常困惑比如，在每个递归级别，以及如何从我的递归中弹出元素 running_vector.

Answer 1

一种可能的方法是使用不同长度的 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][=提取对应的元素17=]

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

Answer 2

这是一个非递归函数。输出是一个矩阵列表，每个矩阵都有对应于所需向量的列。

non_recursive_function <- function(X){
  N <- length(X)
  X2 <- X[-c(1, N)]
  res <- lapply(seq_along(X2), function(k) t(combn(X2, k)))
  inx <- lapply(res, function(x){
    apply(x, 1, function(y) all(diff(y) > 0))
  })
  res <- lapply(seq_along(res), function(i) res[[i]][inx[[i]], ])
  res <- res[sapply(res, length) > 0]
  res <- lapply(res, function(x) 
    apply(as.matrix(x), 1, function(y) c(X[1], y, X[N])))
  res
}

all_points <- c(1, 4, 2, 12, 6, 5, 25)
x <- non_recursive_function(all_points)

在 R 中查找值与约束的组合

Finding combinations of values with constraints in R

recursion

loops

r

constraints

tree-traversal