计算特定约束条件下的排列

Question

我想存储大小为 24 的目标向量的所有可行排列，该向量由 (0,1) 组成。

为了提高内存效率，我使用以下内容：

Test = data.table(permutations(n = 2,r = 12,v = c("zero","one"),repeats.allowed = T))
Test[, names(Test) := lapply(.SD, function(x) gsub("zero", "0,0", x))]
Test[, names(Test) := lapply(.SD, function(x) gsub("one", "1,1", x))]

最终输出应遵循以下内容：

矢量中间连续 1 的最小数量为 8，最大数量为 15。
在start/end只允许连续的1小于8
连续 1 之间有两个 0

示例：

c(1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1) - 正确

c(1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1) - 正确

c(1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0) - 正确

c(0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0) - 正确

c(0,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1) - 错误：只有 2 个连续的 1

c(0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,1) - 错误：向量末尾的连续 1 之间只有一个 0

Answer 1

不确定我是否完全理解，对于中间大量连续的，这里有一些开始：

N <- 24

k <- 15L
npad <- 2L
m <- N - k - 2*npad
apply(expand.grid(0L:1L, 0L:1L, 1L:m), 1L, function(x) {
    y <- rep.int(c(x["Var1"], 0L, 1L, 0L, x["Var2"]), 
        c(x["Var3"], 2L, k, 2L, m - x["Var3"]))
    paste(y, collapse="")
})

k=15 的输出：

 [1] "000111111111111111000000" "100111111111111111000000" "000111111111111111001111" "100111111111111111001111"
 [5] "000011111111111111100000" "110011111111111111100000" "000011111111111111100111" "110011111111111111100111"
 [9] "000001111111111111110000" "111001111111111111110000" "000001111111111111110011" "111001111111111111110011"
[13] "000000111111111111111000" "111100111111111111111000" "000000111111111111111001" "111100111111111111111001"
[17] "000000011111111111111100" "111110011111111111111100" "000000011111111111111100" "111110011111111111111100"

是否也需要 111111111111111000000000 和 011111111111111100000000？如果是，则需要针对 0L 和 1L 的值循环上述内容，而不仅仅是 2L

k=8 的输出：

 [1] "000111111110000000000000" "100111111110000000000000" "000111111110011111111111" "100111111110011111111111"
 [5] "000011111111000000000000" "110011111111000000000000" "000011111111001111111111" "110011111111001111111111"
 [9] "000001111111100000000000" "111001111111100000000000" "000001111111100111111111" "111001111111100111111111"
[13] "000000111111110000000000" "111100111111110000000000" "000000111111110011111111" "111100111111110011111111"
[17] "000000011111111000000000" "111110011111111000000000" "000000011111111001111111" "111110011111111001111111"
[21] "000000001111111100000000" "111111001111111100000000" "000000001111111100111111" "111111001111111100111111"
[25] "000000000111111110000000" "111111100111111110000000" "000000000111111110011111" "111111100111111110011111"
[29] "000000000011111111000000" "111111110011111111000000" "000000000011111111001111" "111111110011111111001111"
[33] "000000000001111111100000" "111111111001111111100000" "000000000001111111100111" "111111111001111111100111"
[37] "000000000000111111110000" "111111111100111111110000" "000000000000111111110011" "111111111100111111110011"
[41] "000000000000011111111000" "111111111110011111111000" "000000000000011111111001" "111111111110011111111001"
[45] "000000000000001111111100" "111111111111001111111100" "000000000000001111111100" "111111111111001111111100"

计算特定约束条件下的排列

Compute permutations following specific constraints

r

data.table

permutation

circular-permutations