3

コンテンツが文字のベクトルであるリストのリストがあります。例えば：

yoda <- list(a=list(c("A","B","C"), c("B","C","D")), b=list(c("D","C"), c("B","C","D","E","F")))

これは私が実際にやろうとしているものよりもはるかに短いバージョンです。私にとっては、それぞれが約12のサブリストを持つ11のリストメンバーがいます。リストメンバーごとに、1つのサブメンバーリストを選択する必要があります。「a」用に1つのリスト、「b」用に1つのリスト。サブリストのどの組み合わせが最大数の一意の値を与えるかを見つけたいと思います。この単純な例では、「a」の最初のサブリストと「b」の2番目のサブリストが最終的な答えを示します。

c("A","B","C","D","E","F")

現時点では、ネストされたループが大量にあり、それは永遠に続くようです。コードの貧弱な部分は次のとおりです。

res <- list()
for (a in 1:length(extra.pats[[1]])) {
  for (b in 1:length(extra.pats[[2]])) {
    for (c in 1:length(extra.pats[[3]])) {
      for (d in 1:length(extra.pats[[4]])) {
        for (e in 1:length(extra.pats[[5]])) {
          for (f in 1:length(extra.pats[[6]])) {
            for (g in 1:length(extra.pats[[7]])) {
              for (h in 1:length(extra.pats[[8]])) {
                for (i in 1:length(extra.pats[[9]])) {
                  for (j in 1:length(extra.pats[[10]])) {
                    for (k in 1:length(extra.pats[[11]])) {
                      res[[paste(a,b,c,d,e,f,g,h,i,j,k, sep="_")]] <- unique(extra.pats[[1]][[a]], extra.pats[[2]][[b]], extra.pats[[3]][[c]], extra.pats[[4]][[d]], extra.pats[[5]][[e]], extra.pats[[6]][[f]], extra.pats[[7]][[g]], extra.pats[[8]][[h]], extra.pats[[9]][[i]], extra.pats[[10]][[j]], extra.pats[[11]][[k]])
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

誰かがこれを適切に行う方法について何かアイデアを持っているなら、それは素晴らしいことです。

4

2 に答える 2

3

提案は次のとおりです。

# create all possible combinations
comb <- expand.grid(yoda)

# find unique values for each combination
uni <- lapply(seq(nrow(comb)), function(x) unique(unlist(comb[x, ])))

# count the unique values
len <- lapply(uni, length)

# extract longest combination  
uni[which.max(len)]

[[1]]
[1] "A" "B" "C" "D" "E" "F"
于 2013-01-22T15:37:13.580 に答える
2

現在の問題の次元では、徹底的な検索が禁止されています。これは、次善のアルゴリズムの例です。単純ですが、「十分に良い」結果が得られることがわかるかもしれません。

アルゴリズムは次のようになります。

  1. 最初のリストを見てください。一意の値の数が最も多いアイテムを選択してください。
  2. 2番目のリストを見てください。手順1ですでに選択したものに加えて、新しい一意の値の数が最も多いアイテムを選択してください。
  3. リストの最後に到達するまで繰り返します。

コード：

good.cover <- function(top.list) {
    selection <- vector("list", length(top.list))
    num.new.unique <- function(x, y) length(setdiff(y, x))
    for (i in seq_along(top.list)) {
        score <- sapply(top.list[[i]], num.new.unique, x = unlist(selection))
        selection[[i]] <- top.list[[i]][which.max(score)]
    }
    selection
}

いくつかのデータを作りましょう：

items.universe <- apply(expand.grid(list(LETTERS, 0:9)), 1, paste, collapse = "")
random.length  <- function()sample(3:6, 1)
random.sample  <- function(i)sample(items.universe, random.length())
random.list    <- function(i)lapply(letters[1:12], random.sample)
initial.list   <- lapply(1:11, random.list)

今それを実行します：

system.time(final.list <- good.cover(initial.list))
#    user  system elapsed 
#   0.004   0.000   0.004
于 2013-01-23T02:23:19.107 に答える