In R: Want to find all "subvectors" with a specific length (9) from a large vector (length 300) , such that the elements sum to a given value

Question

I'd like to find a way to list all the subvectors from the vector of salaries below, with the requirement that their sum lies between 54,000 and 55,000. I've tried using this method in C, but it takes way too long...I think because it finds the vectors before applying the limits (54,000 < sum(vector) < 55,000). Is there a way to improve on this, and preferably do it in R?

I've asked a friend about this, and he suggests developing a method to apply the sum limits as you go; because otherwise, the program would have to find (300 C 9) ~ 4.8 x 10^16 combinations.

Thanks!

Here's the list of salaries:

What do you mean by, "apply the sum limits as you go"? And can you clarify what you mean by "subvector" (i.e. must the elements of the subvector be a continuous subset of the original vector, simply any combination of elements, etc)? — Joshua Ulrich, Nov 26 '14 at 14:49

score 0 · Answer 1 · answered Dec 21 '21 at 17:39

A bit of a belated response, but it might still be useful to somebody.

The idea is to generate all possible subvectors. Since the length of the vector is 320, there is 1 subvector of length 320, 2 subvectors of length 319, 3 subvectors of length 318, ..., and 320 subvectors of length 1. (Note these subvectors are not necessarily unique.) The number of possible subvectors is therefore "only" 321*320/2 = 51360.

Given the above, and assuming x <- c(10800, 9800, 9600, 9600, ..., 3000), the solution should be fairly self-explanatory:

# All possible start and end positions of subvectors
subvectors <- expand.grid(start=1:length(x), end=1:length(x))
# Of course, start must come before end
subvectors <- subvectors[subvectors$start <= subvectors$end, ]
# All possible subvectors
subvectors$values <- apply(subvectors, MARGIN=1, function(r) x[r[1]:r[2]])
# Subvector lengths (for convenience)
subvectors$length <- sapply(subvectors$values, length)
# Subvector sums
subvectors$sum <- sapply(subvectors$values, sum)
# All subvectors that satisfy the constraint
solutions <- subvectors[subvectors$sum >= 53000 & subvectors$sum <= 54000, ]

There are 65 solutions, with lengths ranging from 6 to 17.

Unlike the C solution mentioned above, this is more of a brute force method (O(n³)?), but it's simple enough and still takes just 1 second to run.

In R: Want to find all "subvectors" with a specific length (9) from a large vector (length 300) , such that the elements sum to a given value

1 Answers1