一一绘制二元向量的条件组合

Question

我正在尝试编写一个例程来有条件地查找二元向量的组合。例如，考虑以下向量：

> A <- rep(c(1,0,0),3)
> A
[1] 1 0 0 1 0 0 1 0 0

注意，向量A的长度总是3的倍数，所以下面的条件总是成立：

length(A) %% 3 == 0

主要条件是每组连续的3个向量中必须只有一个1。在这个例子中，比如A[1:3]的一个元素为1，A[4:6]的一个元素为1，A[7:9]的一个元素为1，其余都是0. 因此，对于这个例子，总共会有27种可能的组合。

Objective就是套路draw/return下一个有效组合，直到返回所有可能的合法组合。

请注意，我不是在寻找具有所有可能组合的 table。已在我在 Whosebug 中的其他查询中可用。但是，使用该方法，当 A 中超过 45 个元素的长度时，我运行陷入内存问题，因为它返回的是巨大的完整矩阵。因此，我不想存储完整的矩阵，而是想一次检索一个组合，然后再决定是否要存储它。

Answer 1

OP追求的是一个迭代器。如果我们要正确地做到这一点，我们将使用 get_next 方法在 C++ 中编写一个 class，并将其公开给 R。就目前而言，对于基础 R，由于一切都是按值传递的，我们必须在我们的待更新对象上调用一个函数，并且每次都重新分配要更新的对象。

这是一个非常粗略的实现：

get_next <- function(comb, v, m) {
    s <- seq(1L, length(comb), length(v))
    e <- seq(length(v), length(comb), length(v))
    
    last_comb <- rev(v)
    can_be_incr <- sapply(seq_len(m), function(x) {
        !identical(comb[s[x]:e[x]], last_comb)
    })

    if (all(!can_be_incr)) {
        return(FALSE)
    } else {
        idx  <- which(can_be_incr)[1L]
        span <- s[idx]:e[idx]
        j <- which(comb[span] == 1L)
        comb[span[j]] <- 0L
        comb[span[j + 1L]] <- 1L
        
        if (idx > 1L) {
            ## Reset previous maxed out sections
            for (i in 1:(idx - 1L)) {
                comb[s[i]:e[i]] <- v
            }
        }
    }
    
    return(comb)
}

这是一个简单的用法：

m <- 3L
v <- as.integer(c(1,0,0))
comb <- rep(v, m)
count <- 1L

while (!is.logical(comb)) {
    cat(count, ": ", comb, "\n")
    comb <- get_next(comb, v, m)
    count <- count + 1L
}

1 :  1 0 0 1 0 0 1 0 0 
2 :  0 1 0 1 0 0 1 0 0 
3 :  0 0 1 1 0 0 1 0 0 
4 :  1 0 0 0 1 0 1 0 0 
5 :  0 1 0 0 1 0 1 0 0 
6 :  0 0 1 0 1 0 1 0 0 
7 :  1 0 0 0 0 1 1 0 0 
8 :  0 1 0 0 0 1 1 0 0 
9 :  0 0 1 0 0 1 1 0 0 
10 :  1 0 0 1 0 0 0 1 0 
11 :  0 1 0 1 0 0 0 1 0 
12 :  0 0 1 1 0 0 0 1 0 
13 :  1 0 0 0 1 0 0 1 0 
14 :  0 1 0 0 1 0 0 1 0 
15 :  0 0 1 0 1 0 0 1 0 
16 :  1 0 0 0 0 1 0 1 0 
17 :  0 1 0 0 0 1 0 1 0 
18 :  0 0 1 0 0 1 0 1 0 
19 :  1 0 0 1 0 0 0 0 1 
20 :  0 1 0 1 0 0 0 0 1 
21 :  0 0 1 1 0 0 0 0 1 
22 :  1 0 0 0 1 0 0 0 1 
23 :  0 1 0 0 1 0 0 0 1 
24 :  0 0 1 0 1 0 0 0 1 
25 :  1 0 0 0 0 1 0 0 1 
26 :  0 1 0 0 0 1 0 0 1 
27 :  0 0 1 0 0 1 0 0 1

请注意，此实现将提高内存效率，但速度会很慢。

一一绘制二元向量的条件组合

Drawing conditional combinations of a binary vector one by one

r

matrix

conditional-statements

sparse-matrix

combinatorics