R递归地创建基于唯一性和重叠因子的解决方案集

Question

我有一组解决方案，但我试图通过使用最大重叠来解析它们，使它们彼此更加不同。这是解决方案集（以及 0 和 1 的视图 - 它们是指示是否选择了 A-F 的二进制变量），我的伪代码试图解决它（代码下方有更多详细信息）：

solutions <- list(c(1, 0, 0, 1, 1, 1), c(0, 1, 0, 0, 1, 1), c(0, 1, 0, 1, 1, 1), c(1, 0, 0, 1, 0, 1))

1 0 0 1 1 1
0 1 0 0 1 1
0 1 0 1 1 1
1 0 0 1 0 1

# Pseudocode attempt
k = 2 #max allowed overlaps
i = 1 #counter

final_solutions <- list() #list of final solutions that are valid

while (i <= length(solutions)) {
    if (i == 1) { #putting the first solution in, no checking
        final_solutions[i] <- solutions[[i]]
    }
    j = 0 #number of overlaps 
    for (member in final_solutions) { #iterate through all solutions that have been validated
        if overlap(solution[[i]], member) > k {
              j = j + 1
        }
    }
    if (j == 0) { final_solutions <- append(final_solutions, solution[[i]]) }
}

基本上，我现在正在尝试遍历此列表，并且只保留与集合中的其他解决方案最多共享两个公共 1 的解决方案。

所以，首先我会采用第一个解决方案 (1, 0, 0, 1, 1, 1) 并将其添加到我的集合中。

接下来我将查看 (0, 1, 0, 0, 1, 1)。它在最后两个位置与第一个解决方案共享 1，所以没关系，它会被添加。

接下来看第三种解法，(0, 1, 0, 1, 1, 1)。它与第一个解决方案共享最后三个位置的 1，以及与第二个解决方案共享第二个 1 和最后两个 1。它不会添加到集合中。

最后，看第四个解(1, 0, 0, 1, 0, 1) - 它的三个1与第一个解共享，所以没有添加。

我在想类似于上面的伪代码的东西，但我将不胜感激任何帮助/修复该语法的帮助，因为我对列表不是很好！

Answer 1

如果你想要一种递归的方式，这里可能是通过定义递归函数的一种选择f

f <- function(lst) {
  if (length(lst) == 1) {
    return(lst)
  }
  nlst <- tail(lst, 1)
  plst <- head(lst, -1)
  v <- Recall(plst)
  if (all(nlst[[1]] %*% do.call(cbind,plst) <= 2)) {
    v <- c(v, nlst)
  }
  v
}

你会看到

> f(solutions)
[[1]]
[1] 1 0 0 1 1 1

[[2]]
[1] 0 1 0 0 1 1

或者，我们可以使用 Reduce 但遵循相同的想法

Reduce(
  function(x, y) {
    if (all(y %*% do.call(cbind, x) <= 2)) {
      return(c(x, list(y)))
    }
    x
  },
  solutions[-1],
  init = solutions[1]
)

这给出了

[[1]]
[1] 1 0 0 1 1 1

[[2]]
[1] 0 1 0 0 1 1

R递归地创建基于唯一性和重叠因子的解决方案集

R Recursively Create Set of Solutions Based on Uniqueness and Overlap Factor

algorithm

recursion

r

list