Find all combinations with cost in range

combos.R

library(dplyr)

# invent some data
budget_min = 2e4
budget_max = 2.5e4
costs = round(rnorm(n=20, mean=1e4, sd=3e3))
names(costs) = LETTERS[1:20]


# Find upper and lower bounds on number of projects in an affordable combination
n_low = floor(budget_min/max(costs))
n_high = ceiling(budget_max/min(costs))

is_affordable = function(x, min = budget_min, max = budget_max){
	if(sum(x) < min || sum(x) > max){ 
		return(NULL)
	}
	x
}

choose_n_affordable = function(n, candidates){
	if(choose(length(candidates), n) > 1e5){
		stop("More than 1e5 possible combinations of ", n, ". You probably don't want to brute-force this one, Chris")
	}
	combn(x = candidates, m = n, FUN = is_affordable, simplify = FALSE)
}

all_combos = sapply((n_low):(n_high), choose_n_affordable, costs)

viable_combos = (all_combos 
	%>% purrr::flatten()
	%>% purrr::compact())




# Some token analysis:
# 1. Which projects appear most frequently in the viable solutions?
viable_combos %>% purrr::map(names) %>% purrr::flatten_chr() %>% table() %>% sort()

# O  M  N  A  I  T  R  J  P  F  H  Q  G  S  E  B  L  C  K  D 
# 5 11 11 12 12 12 14 22 22 24 27 27 28 28 32 41 41 46 54 71 

# 2. How are the total costs of viable combinations distributed?
viable_combos %>% purrr::map(sum) %>% purrr::flatten_dbl() %>% stem(scale=0.5)

#  The decimal point is 3 digit(s) to the right of the |
#
#  20 | 1344
#  20 | 56778899999
#  21 | 001112222333334444
#  21 | 556677778889999
#  22 | 0112233333333344
#  22 | 55555666777788888899999
#  23 | 0000112222233333334444
#  23 | 55556666677777788888888899
#  24 | 0000000011112222222222333334444444
#  24 | 55555666666777777788888888999999
#  25 | 00

Beware: Brute-force approach. Will probably melt your laptop if n_projects is large, or even if n_projects is moderate but n_per_combo is close to n_projects/2.