Поиск всех возможных комбинаций чисел из вектора для достижения заданной суммы (без повторов) - PullRequest
Новая
       4

Поиск всех возможных комбинаций чисел из вектора для достижения заданной суммы (без повторов)

3 голосов
/ 23 апреля 2019

У меня есть вектор «числа», и я хочу выяснить все возможные комбинации из 1,2 или 3 чисел, которые суммируются в диапазоне от 90 до 110.

Я знаю, что есть многопосты со способами решения проблемы, но ни один из них не делает то, что мне нужно.По крайней мере, не в R # 

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

Результат должен выглядеть следующим образом: 

A + B
A + D
A + H
I
B + E
B + F
C + H
C + J
C + K
D + E
D + F
F + H
F + K
J + L

Ответы [ 5 ]

6 голосов
/ 24 апреля 2019

Я создал пакет под названием RcppAlgos, созданный для этих задач.Существует функция comboGeneral, которая может найти все комбинации в соответствии с определенным ограничением.Заметьте: 

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 = " + ")
    }))
}

Вот пример: 

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"

Он достаточно эффективен, как и написано в C++ для максимальной производительности.

4 голосов
/ 23 апреля 2019

В приведенном ниже коде мы определяем комбинации значений с суммами в требуемом диапазоне, а затем получаем индексы этих комбинаций. Затем мы используем индексы, чтобы получить имена элементов, которые мы хотим суммировать вместе. lapply выполняет итерацию для каждого числа значений, которые мы хотим суммировать.

Это упаковано в функцию, где x - именованный вектор чисел, n - максимальное количество значений, которые вы хотите суммировать вместе, а interval - диапазон, в котором должны быть суммы.

Обратите внимание, что нижеприведенная функция возвращает строки вида "A + B", как описано в вашем вопросе. Если ваша цель состоит в том, чтобы выполнить дополнительную обработку комбинаций букв, вам, вероятно, будет лучше работать напрямую с матрицами (или списками) комбинаций, возвращаемых combn(). 

numbers <- c(40,60,20,65,45,30,5,70,100,85,75,10);
names(numbers) <- LETTERS[1:length(numbers)]

library(dplyr) # For between function

combos = function(x, n, interval) {

  res = lapply(2:n, function(i) {
    cc = combn(x, i)
    idx = which(between(colSums(cc), interval[1], interval[2]))
    apply(combn(names(x), i)[ , idx], 2, paste, collapse=" + ")
  })

  cbind(unlist(c(names(x)[between(x, interval[1], interval[2])], res)))
}

combos(numbers, 3, c(90, 110))

     [,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"

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

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

      [,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"
2 голосов
/ 24 апреля 2019

Рекурсивная опция без генерации всех комбинаций.Может быть эффективным с точки зрения памяти, но, конечно, не быстро. 

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=" + ")))

вывод: 

 [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"
2 голосов
/ 23 апреля 2019

Вот решение для комбинации из двух и трех чисел. Я оставляю это на усмотрение читателя на 1 комбинацию цифр: 

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"
1 голос
/ 23 апреля 2019

Я бы создал список всех возможных m комбинаций из n элементов (m = 1, 2, 3), используя combn.Затем вы можете суммировать элементы в каждом кортеже и фильтровать их по требуемому диапазону.Извините за очень приблизительный ответ, так как в данный момент у меня нет доступа к ПК.

...