Trouver toutes les combinaisons possibles de nombres à partir d'un vecteur pour atteindre une somme donnée (pas de répétitions)

Je créerais une liste de toutes les m combinaisons possibles de n éléments (m = 1, 2, 3) en utilisant combn. Vous pouvez ensuite additionner les éléments de chaque tuple et les filtrer selon la plage souhaitée. Désolé pour la réponse très approximative car je n'ai pas accès à un PC pour le moment.

Dans le code ci-dessous, nous identifions les combinaisons de valeurs avec des sommes dans la plage souhaitée, puis obtenons les indices de ces combinaisons. Nous utilisons ensuite les indices pour obtenir les noms des éléments que nous voulons additionner. lapply s'occupe d'itérer sur chaque nombre de valeurs que nous voulons additionner.

Ceci est emballé dans une fonction où x est le vecteur nommé de nombres, n est le nombre maximum de valeurs que vous souhaitez additionner, et interval est la plage dans laquelle les sommes devraient être.

Notez que la fonction ci-dessous renvoie des chaînes de la forme "A + B" , comme décrit dans votre question. Si votre objectif est de faire un traitement supplémentaire sur les combinaisons de lettres, vous ferez probablement mieux de travailler directement avec les matrices (ou listes) de combinaisons renvoyées par combn () .

XXX

      [,1]       
 [1,] "B + I"    
 [2,] "C + G"    
 [3,] "F + I"    
 [4,] "B + C + G"
 [5,] "B + E + I"
 [6,] "B + F + I"
 [7,] "B + I + J"
 [8,] "C + D + I"
 [9,] "C + E + G"
[10,] "C + F + G"
[11,] "C + G + H"
[12,] "C + G + J"
[13,] "E + F + I"
[14,] "G + H + I"

set.seed(2)
nn = rnorm(10)
names(nn) = LETTERS[1:length(nn)]

combos(nn, 3, c(2,2.5))

     [,1]       
 [1,] "I"        
 [2,] "A + B"    
 [3,] "A + D"    
 [4,] "A + H"    
 [5,] "B + E"    
 [6,] "B + F"    
 [7,] "C + H"    
 [8,] "C + J"    
 [9,] "C + K"    
[10,] "D + E"    
[11,] "D + F"    
[12,] "F + H"    
[13,] "F + K"    
[14,] "G + I"    
[15,] "G + J"    
[16,] "I + L"    
[17,] "J + L"    
[18,] "A + B + G"
[19,] "A + B + L"
[20,] "A + C + E"
[21,] "A + C + F"
[22,] "A + D + G"
[23,] "A + E + G"
[24,] "A + E + L"
[25,] "B + C + F"
[26,] "B + C + L"
[27,] "B + E + G"
[28,] "B + F + G"
[29,] "B + F + L"
[30,] "C + D + G"
[31,] "C + D + L"
[32,] "C + E + F"
[33,] "C + G + H"
[34,] "C + G + J"
[35,] "C + G + K"
[36,] "C + H + L"
[37,] "C + K + L"
[38,] "D + F + G"
[39,] "D + F + L"
[40,] "F + G + H"
[41,] "F + G + K"
[42,] "F + H + L"
[43,] "G + J + L"
[44,] "G + K + L"

Voici une solution pour la combinaison de deux et trois nombres. Je laisse le soin au lecteur pour 1 cas de combinaison de chiffres:

numbers <- c(40,60,20,65,45,30,5,70,100,85,75,10)
numnames<- c("A","B","C","D","E","F","G","H","I","J","K","L")

#Take 2 at a time
#Find all combinations of 2 each (output is a matrix)
c2<-combn(numbers, 2)
#find column positions which match the critera
mymatch<-which(colSums(c2)>=90 & colSums(c2)<=110)

#get results of letter comibnations
#combn(numnames, 2) will generate the same squence order as combn(numbers, 2)
answer2<-apply(combn(numnames, 2)[,mymatch], 2, function(t){print(t)
  paste(t, collapse = "+" )})

#Repeat taking 3 at a time
c3<-combn(numbers, 3)
mymatch<-which(colSums(c3)>=90 & colSums(c3)<=110)

answer3<-apply(combn(numnames, 3)[,mymatch], 2, function(t){print(t)
  paste(t, collapse = "+" )})

print(c(answer2, answer3))

[1] "A+B"   "A+D"   "A+H"   "B+E"   "B+F"   "C+H"   "C+J"   "C+K"   "D+E"   "D+F"   "F+H"   "F+K"   "G+I"    
[14] "G+J"   "I+L"   "J+L"   "A+B+G" "A+B+L" "A+C+E" "A+C+F" "A+D+G" "A+E+G" "A+E+L" "B+C+F" "B+C+L" "B+E+G"
[27] "B+F+G" "B+F+L" "C+D+G" "C+D+L" "C+E+F" "C+G+H" "C+G+J" "C+G+K" "C+H+L" "C+K+L" "D+F+G" "D+F+L" "F+G+H"
[40] "F+G+K" "F+H+L" "G+J+L" "G+K+L"

J'ai créé un package appelé RcppAlgos qui est conçu pour ces tâches. Il existe une fonction comboGeneral qui est capable de trouver toutes les combinaisons sous une contrainte particulière. Observez:

numbers <- c(40,60,20,65,45,30,5,70,100,85,75,10);
myNames <- c("A","B","C","D","E","F","G","H","I","J","K","L")

comboBetween(numbers, 4, c(90, 110))
 [1] "I"             "G + J"         "G + I"         "L + J"         "L + I"         "C + H"        
 [7] "C + K"         "C + J"         "F + B"         "F + D"         "F + H"         "F + K"        
[13] "A + B"         "A + D"         "A + H"         "E + B"         "E + D"         "G + L + K"    
[19] "G + L + J"     "G + C + D"     "G + C + H"     "G + C + K"     "G + C + J"     "G + F + B"    
[25] "G + F + D"     "G + F + H"     "G + F + K"     "G + A + E"     "G + A + B"     "G + A + D"    
[31] "G + E + B"     "L + C + B"     "L + C + D"     "L + C + H"     "L + C + K"     "L + F + B"    
[37] "L + F + D"     "L + F + H"     "L + A + E"     "L + A + B"     "C + F + A"     "C + F + E"    
[43] "C + F + B"     "C + A + E"     "G + L + C + B" "G + L + C + D" "G + L + C + H" "G + L + C + K"
[49] "G + L + F + E" "G + L + F + B" "G + L + F + D" "G + L + A + E" "G + C + F + A" "G + C + F + E"
[55] "G + C + A + E" "L + C + F + A" "L + C + F + E"

Voici un exemple:

comboBetween <- function(v, m, constraint) {
    do.call(c, lapply(1:m, function(x) {
        nums <- comboGeneral(v, x, constraintFun = "sum", 
                                   comparisonFun = c(">=", "<="), 
                                   limitConstraints = constraint)
        apply(matrix(myNames[match(nums, numbers)], 
                     ncol = x), 1, paste, collapse = " + ")
    }))
}

Il est assez efficace et il est écrit en C ++ code> pour des performances maximales.

Une option récursive sans générer toutes les combinaisons. Peut être efficace en mémoire mais sûrement pas rapide.

 [1] "A + B"     "A + B + G" "A + B + L" "A + C + E" "A + C + F" "A + D"     "A + D + G"
 [8] "A + E + G" "A + E + L" "A + H"     "B + C + F" "B + C + L" "B + E"     "B + E + G"
[15] "B + F"     "B + F + G" "B + F + L" "C + D + G" "C + D + L" "C + E + F" "C + G + H"
[22] "C + G + J" "C + G + K" "C + H"     "C + H + L" "C + J"     "C + K"     "C + K + L"
[29] "D + E"     "D + F"     "D + F + G" "D + F + L" "F + G + H" "F + G + K" "F + H"    
[36] "F + H + L" "F + K"     "G + I"     "G + J"     "G + J + L" "G + K + L" "I"        
[43] "I + L"     "J + L"    

résultat:

gen <- function(chosen, rest, lb, ub) {

    new_ub <- ub - sum(chosen)

    rest <- rest[-match(chosen[1L], rest)]

    if (new_ub < 0 || length(chosen) > 2L || !any(rest <= new_ub)) {
        if (sum(chosen) >= lb && sum(chosen) <= ub) {
            return(list(chosen[order(names(chosen))]))
        }
        return(NULL)
    }

    ret <- c()
    for (x in names(rest[rest <= new_ub])) {
        ret <- c(ret, gen(c(rest[x], chosen), rest, lb, ub))
        if (sum(chosen) >= lb && sum(chosen) <= ub) {
            ret <- c(list(chosen[order(names(chosen))]), ret)
        }
    }
    ret
}

ans <- unique(unlist(
    lapply(names(numbers), function(x) gen(numbers[x], rest=numbers, lb=90, ub=110)),
    recursive=FALSE))
unique(sapply(ans, function(x) paste(sort(names(x)), collapse=" + ")))