列表一起覆盖所有给定的元素

Question

说字符串的所有组合，我给出以下字符串：

1:{a,b,c,t} 
2:{b,c,d} 
3:{a,c,d} 
4:{a,t} 

我想打一个程序，给我这些字符串，其中每个组合有各种不同的组合包括每个给定的字母。 因此，例如上述组合都是字符串{1 & 2,1 & 3,2 4,1 4,2 & 4}。

我正在考虑用for循环来做这件事，在那里程序会查看第一个字符串，找到哪些元素丢失，然后通过列表查找找到具有这些字母的字符串。不过，我认为这个想法只能找到两个字符串的组合，并且它要求列出所有看起来非常不经济的程序。

Answer 1

我认为像这样的东西应该工作。

sets <- list(c('a', 'b', 'c', 't'), 
      c('b', 'c', 'd'), 
      c('a', 'c', 'd'), 
      c('a', 't')) 

combinations <- lapply(2:length(sets), 
         function(x) combn(1:length(sets), x, simplify=FALSE)) 
combinations <- unlist(combinations, FALSE) 
combinations 
# [[1]] 
# [1] 1 2 
# 
# [[2]] 
# [1] 1 3 
# 
# [[3]] 
# [1] 1 4 
# 
# [[4]] 
# [1] 2 3 
# 
# [[5]] 
# [1] 2 4 
# 
# [[6]] 
# [1] 3 4 
# 
# [[7]] 
# [1] 1 2 3 
# 
# [[8]] 
# [1] 1 2 4 
# 
# [[9]] 
# [1] 1 3 4 
# 
# [[10]] 
# [1] 2 3 4 
# 
# [[11]] 
# [1] 1 2 3 4 

u <- unique(unlist(sets)) 
u 
# [1] "a" "b" "c" "t" "d" 

Filter(function(x) length(setdiff(u, unlist(sets[x]))) == 0, combinations) 
# [[1]] 
# [1] 1 2 
# 
# [[2]] 
# [1] 1 3 
# 
# [[3]] 
# [1] 2 4 
# 
# [[4]] 
# [1] 1 2 3 
# 
# [[5]] 
# [1] 1 2 4 
# 
# [[6]] 
# [1] 1 3 4 
# 
# [[7]] 
# [1] 2 3 4 
# 
# [[8]] 
# [1] 1 2 3 4 

Answer 2

作为开始... 我会在有空的时候编辑这个答案。以下结果取决于选择的顺序。我还没有想出如何将名单变平。如果我可以将它压平，我会对每个结果进行排序，然后删除重复项。

v = list(c("a","b","c","t"),c("b","c","d"),c("a","c","d"),c("a","t")) 

allChars <- Reduce(union, v) # [1] "a" "b" "c" "t" "d" 

charInList <- function(ch, li) which(sapply(li, function(vect) ch %in% vect)) 
locations <- sapply(allChars, function(ch) charInList(ch, v)) 
# > locations 
# $a 
# [1] 1 3 4 
# 
# $b 
# [1] 1 2 
# 
# $c 
# [1] 1 2 3 
# 
# $t 
# [1] 1 4 
# 
# $d 
# [1] 2 3 

findStillNeeded<-function(chosen){ 
    haveChars <- Reduce(union, v[chosen]) 
    stillNeed <- allChars[!allChars %in% haveChars] 
    if(length(stillNeed) == 0) return(chosen) #terminate if you dont need any more characters 
    return (lapply(1:length(stillNeed), function(i) { #for each of the characters you still need 
    loc <- locations[[stillNeed[i]]] #find where the character is located 
    lapply(loc, function(j){ 
     findStillNeeded(c(chosen, j)) #when you add this location to the choices, terminate if you dont need any more characters 
    }) 
    })) 

} 

result<-lapply(1:length(v), function(i){ 
    findStillNeeded(i) 
})