CODEWITHSUNDEEP
r
Iason
Iason

Reputation: 39

Unique combinations of vector elements that fulfill criteria

I have a vector of integers, e.g., totalVector <- c(4,2,1), and two variables totalResult and totalNumber. What I want to do is the following:

I want to to find all UNIQUE combinations of "totalNumber" elements from totalVector that add up to "totalResult". To clarify, if totalResult = 100 and totalNumber = 50, I want all combinations of 50 elements from totalVector that have a sum of 100 (repetitions are obviously allowed, but duplicate results such as 25 fours and 25 re-arranged fours should only be counted once).

I originally did this by expanding the total vector (repeating each element 50 times), getting all combinations of 50 elements with combn() and then filtering their sums. For large values however, this proved very inefficient, and failed due to the sheer amount of data. Is there a quicker and less data-heavy way to do this?

Upvotes: 1

Views: 113

Answers (2)

Joseph Wood
Joseph Wood

Reputation: 7597

I think the OP is looking for the combinations with repetition of a vector that sum to a particular number. This will do it:

totalVector <- c(4,2,1)
totalNumber <- 50
totalResult <- 100

library(RcppAlgos)
myAns <- comboGeneral(totalVector, totalNumber, repetition = TRUE,
                      constraintFun = "sum", comparisonFun = "==",
                      limitConstraints = totalResult)

dim(myAns)
[1] 17 50

all(apply(myAns, 1, sum) == totalResult)
[1] TRUE

Disclaimer: I am the author of RcppAlgos

Upvotes: 1

Cleland
Cleland

Reputation: 359

This would give you what you need for a small sample, but you will encounter issues with combinatorial explosion very quickly as you increase the size of the problem

tv <- sample(1:10, 10, replace = TRUE)
tn <- 5
tr <- 20
combinations <- combn(tv, tn)
equals.tr <- apply(combinations, MARGIN = 2, FUN = function(x) sum(x) == tr)
combinations[, equals.tr]

Upvotes: 0

Related Questions