可以连接到 R 中的原始字符串的所有子字符串组合

Question

给定一组 n 个唯一有序的字符，

如何找到可以连接成原始有序字符集（在 R 中）的所有子字符串组合？

例如，对于 n=5，使用以 a 开头的字母字符，输入（作为字符元素）和所需输出（作为字符元素的向量列表）如下所示，

输入：

ordered.chars <- "abcde"

期望的输出：

ord.substr.list <- list(
c("a","b","c","d","e"),
c("ab","c","d","e"),
c("ab","cd","e"),
c("ab","c","de"),
c("a","bc","d","e"),
c("a","bc","de"),
c("a","b","cd","e"),
c("a","b","c","de"),
c("abc","d","e"),
c("abc","de"),
c("a","bcd","e"),
c("a","b","cde"),
c("ab","cde"),
c("abcd","e"),
c("a","bcde"))

所有列出的字符元素向量连接成原始字符元素的条件测试：

all(unlist(lapply(ord.substr.list, function(x) paste(x, collapse=""))) %in% ordered.chars)

我的 google/Whosebug 搜索导致 combn()，它在类似情况下很有用，但在这里似乎没有明显帮助。

Answer 1

问题的核心是能够生成 power set。

这里有一个使用RcppAlgos的解决方案（我是作者）。

library(RcppAlgos)

customPowSetStr <- function(n) {
    len <- n * 2 - 1
    v <- vector("character", length = len)
    v[seq(1, len, 2)] <- letters[1:n]
    v[seq(2, len, 2)] <- ","

    comboGeneral(0:(n - 1), n - 1, freqs = c(n - 2, rep(1, n - 1)), FUN = function(x) {
        temp <- v
        strsplit(paste0(temp[-(x[x > 0] * 2)], collapse = ""), ",")[[1]]
    })
}

customPowSetStr(5)
[[1]]
[1] "ab" "c"  "d"  "e" 

[[2]]
[1] "a"  "bc" "d"  "e" 

[[3]]
[1] "a"  "b"  "cd" "e" 

[[4]]
[1] "a"  "b"  "c"  "de"

[[5]]
[1] "abc" "d"   "e"  

[[6]]
[1] "ab" "cd" "e" 

[[7]]
[1] "ab" "c"  "de"

[[8]]
[1] "a"   "bcd" "e"  

[[9]]
[1] "a"  "bc" "de"

[[10]]
[1] "a"   "b"   "cde"

[[11]]
[1] "abcd" "e"   

[[12]]
[1] "abc" "de" 

[[13]]
[1] "ab"  "cde"

[[14]]
[1] "a"    "bcde"

[[15]]
[1] "abcde"

可以连接到 R 中的原始字符串的所有子字符串组合

All combinations of substrings that can be concatenated into the original string in R

string

substring

r

combinatorics