高效枚举 R 中具有差异约束的所有子集

Question

我有一个由长度为

V

的连续整数组成的向量

l

，例如

1, 2, 3, 4, 5, 6, 7

。我想找到大小为

k

的所有子集，使得子集中任意两个数字之间的差值不能小于

m

，例如

2

。使用上面的示例以及

l = 7

、

k = 3

和

m = 2

，子集为

1, 3, 5
1, 3, 6
1, 3, 7
1, 4, 6
1, 4, 7
1, 5, 7
2, 4, 6
2, 4, 7
2, 5, 7
3, 5, 7

一种方法是枚举大小为

k

的所有可能子集，并丢弃任何无法满足

m

约束的子集，但即使解数很少，此过程也会爆炸。

我当前的方法是一种暴力算法，其中我从具有最小可能整数的子集开始，将最后一个条目增加 1，直到达到上限，增加前一个条目并将最后一个条目重置为可以的最低值给予前一个条目的增加。也就是说，我从

1, 3, 5

开始，然后将最后一位数字加一以获得

1, 3, 6

和

1, 3, 7

，然后由于达到上限，我将中间加 1（到

4

）并设置最后一位数字到最小，可以给定该数字（到

6

）以获得

1, 4, 6

，并继续下去。对于大的

l

，这最终在 R 中相当慢，我想知道是否有一个聪明的矢量化解决方案可以立即生成所有组合，这可以通过利用条目的顺序性质来实现。在

Rcpp

中实现这个算法会稍微加快速度，但我仍然希望有一个更优雅的解决方案（如果有的话）。

Answer 1

一个合理的方法可能是在给定的约束下递归地构建向量：

f <- function(v, k, m, existing = numeric()) {
  new_vals <- min(v):(max(v) - ((k - 1) * m))
  updated <- lapply(new_vals, function(x) c(existing, x))
  if(k == 1) return(updated)
  purrr::list_flatten(lapply(updated, function(x) {
    if((max(x) + m) == max(v)) return(c(x, max(v)))
    if(max(x) + m > max(v)) return(x)
    f(v[v >= (max(x) + m)], k - 1, m, x)
  }))
}

这为我们提供了给定启动参数的相同列表：

f(v = 1:7, k = 3, m = 2)
#> [[1]]
#> [1] 1 3 5
#> 
#> [[2]]
#> [1] 1 3 6
#> 
#> [[3]]
#> [1] 1 3 7
#> 
#> [[4]]
#> [1] 1 4 6
#> 
#> [[5]]
#> [1] 1 4 7
#> 
#> [[6]]
#> [1] 1 5 7
#> 
#> [[7]]
#> [1] 2 4 6
#> 
#> [[8]]
#> [1] 2 4 7
#> 
#> [[9]]
#> [1] 2 5 7
#> 
#> [[10]]
#> [1] 3 5 7

并正确找到向量 1:10 中唯一 k = 4 且 m = 3 的集合

f(v = 1:10, k = 4, m = 3)
#> [[1]]
#> [1]  1  4  7 10

或者 1:10 中 k = 3, m = 2 的大集合

f(v = 1:10, k = 3, m = 2)
#> [[1]]
#> [1] 1 3 5
#> 
#> [[2]]
#> [1] 1 3 6
#> 
#> [[3]]
#> [1] 1 3 7
#> 
#> [[4]]
#> [1] 1 3 8
#> 
#> [[5]]
#> [1] 1 3 9
#> 
#> [[6]]
#> [1]  1  3 10
#> 
#> [[7]]
#> [1] 1 4 6
#> 
#> [[8]]
#> [1] 1 4 7
#> 
#> [[9]]
#> [1] 1 4 8
#> 
#> [[10]]
#> [1] 1 4 9
#> 
#> [[11]]
#> [1]  1  4 10
#> 
#> [[12]]
#> [1] 1 5 7
#> 
#> [[13]]
#> [1] 1 5 8
#> 
#> [[14]]
#> [1] 1 5 9
#> 
#> [[15]]
#> [1]  1  5 10
#> 
#> [[16]]
#> [1] 1 6 8
#> 
#> [[17]]
#> [1] 1 6 9
#> 
#> [[18]]
#> [1]  1  6 10
#> 
#> [[19]]
#> [1] 1 7 9
#> 
#> [[20]]
#> [1]  1  7 10
#> 
#> [[21]]
#> [1]  1  8 10
#> 
#> [[22]]
#> [1] 2 4 6
#> 
#> [[23]]
#> [1] 2 4 7
#> 
#> [[24]]
#> [1] 2 4 8
#> 
#> [[25]]
#> [1] 2 4 9
#> 
#> [[26]]
#> [1]  2  4 10
#> 
#> [[27]]
#> [1] 2 5 7
#> 
#> [[28]]
#> [1] 2 5 8
#> 
#> [[29]]
#> [1] 2 5 9
#> 
#> [[30]]
#> [1]  2  5 10
#> 
#> [[31]]
#> [1] 2 6 8
#> 
#> [[32]]
#> [1] 2 6 9
#> 
#> [[33]]
#> [1]  2  6 10
#> 
#> [[34]]
#> [1] 2 7 9
#> 
#> [[35]]
#> [1]  2  7 10
#> 
#> [[36]]
#> [1]  2  8 10
#> 
#> [[37]]
#> [1] 3 5 7
#> 
#> [[38]]
#> [1] 3 5 8
#> 
#> [[39]]
#> [1] 3 5 9
#> 
#> [[40]]
#> [1]  3  5 10
#> 
#> [[41]]
#> [1] 3 6 8
#> 
#> [[42]]
#> [1] 3 6 9
#> 
#> [[43]]
#> [1]  3  6 10
#> 
#> [[44]]
#> [1] 3 7 9
#> 
#> [[45]]
#> [1]  3  7 10
#> 
#> [[46]]
#> [1]  3  8 10
#> 
#> [[47]]
#> [1] 4 6 8
#> 
#> [[48]]
#> [1] 4 6 9
#> 
#> [[49]]
#> [1]  4  6 10
#> 
#> [[50]]
#> [1] 4 7 9
#> 
#> [[51]]
#> [1]  4  7 10
#> 
#> [[52]]
#> [1]  4  8 10
#> 
#> [[53]]
#> [1] 5 7 9
#> 
#> [[54]]
#> [1]  5  7 10
#> 
#> [[55]]
#> [1]  5  8 10
#> 
#> [[56]]
#> [1]  6  8 10

^{创建于 2023-08-24，使用 reprex v2.0.2}