How to find the vector's values (only integers) which satisfies some linear constraints in R?

Question

Given a vector and a sum, for example limits = c(1,2,5,6,7,6) and sum = 10. The given constrains are:

1. x1 <= limits[1]

2. x2 <= limits[2]

3. x3 <= limits[3]

4. x4 <= limits[4]

5. x5 <= limits[5]

6. x6 <= limits[6]

7. x1+x2+x3+x4+x5+x6 = sum

I'd like to find a single vector: c(x1,x2,x3,x4,x5,x6) which satisfy those constrains. I wrote this:

get_vector <-function(sum, limits){

  res_vec <-c()
  left <- sum

  for (i in seq(1:(length(limits)-1))){
    res_vec<-c(res_vec, sample(c(0:min(limits[i],left)), 1))
    left <- left - res_vec[i]
  }

   res_vec[length(limits)] <- left

  }

  return (res_vec)
}

but it seems to fail from time to time (I have checked it). Can someone give a more accurate suggestion how to solve this?

Thank you

Answer 1

Here is a way to get all possible solutions.

library(partitions)

allPartitions <- compositions(10, 6, include.zero = FALSE)
limits <- c(1, 2, 5, 6, 7, 6) 
good <- apply(allPartitions, 2, function(x) all(x <= limits))
results <- allPartitions[, good]

---

> t(results)
      [,1] [,2] [,3] [,4] [,5] [,6]
 [1,]    1    2    4    1    1    1
 [2,]    1    1    5    1    1    1
 [3,]    1    2    3    2    1    1
 [4,]    1    1    4    2    1    1
 [5,]    1    2    2    3    1    1
 [6,]    1    1    3    3    1    1
 [7,]    1    2    1    4    1    1
 [8,]    1    1    2    4    1    1
 [9,]    1    1    1    5    1    1
[10,]    1    2    3    1    2    1
[11,]    1    1    4    1    2    1
[12,]    1    2    2    2    2    1
[13,]    1    1    3    2    2    1
[14,]    1    2    1    3    2    1
[15,]    1    1    2    3    2    1
[16,]    1    1    1    4    2    1
[17,]    1    2    2    1    3    1
[18,]    1    1    3    1    3    1
[19,]    1    2    1    2    3    1
[20,]    1    1    2    2    3    1
[21,]    1    1    1    3    3    1
[22,]    1    2    1    1    4    1
[23,]    1    1    2    1    4    1
[24,]    1    1    1    2    4    1
[25,]    1    1    1    1    5    1
[26,]    1    2    3    1    1    2
[27,]    1    1    4    1    1    2
[28,]    1    2    2    2    1    2
[29,]    1    1    3    2    1    2
[30,]    1    2    1    3    1    2
[31,]    1    1    2    3    1    2
[32,]    1    1    1    4    1    2
[33,]    1    2    2    1    2    2
[34,]    1    1    3    1    2    2
[35,]    1    2    1    2    2    2
[36,]    1    1    2    2    2    2
[37,]    1    1    1    3    2    2
[38,]    1    2    1    1    3    2
[39,]    1    1    2    1    3    2
[40,]    1    1    1    2    3    2
[41,]    1    1    1    1    4    2
[42,]    1    2    2    1    1    3
[43,]    1    1    3    1    1    3
[44,]    1    2    1    2    1    3
[45,]    1    1    2    2    1    3
[46,]    1    1    1    3    1    3
[47,]    1    2    1    1    2    3
[48,]    1    1    2    1    2    3
[49,]    1    1    1    2    2    3
[50,]    1    1    1    1    3    3
[51,]    1    2    1    1    1    4
[52,]    1    1    2    1    1    4
[53,]    1    1    1    2    1    4
[54,]    1    1    1    1    2    4
[55,]    1    1    1    1    1    5

Or, more concisely and perhaps more efficient:

> results <- sweep(blockparts(limits-1,10-6), 1, c(1,1,1,1,1,1), "+")
> t(results)

 [1,] 1 2 4 1 1 1
 [2,] 1 1 5 1 1 1
 [3,] 1 2 3 2 1 1
 [4,] 1 1 4 2 1 1
 [5,] 1 2 2 3 1 1
 [6,] 1 1 3 3 1 1
 [7,] 1 2 1 4 1 1
 [8,] 1 1 2 4 1 1
 [9,] 1 1 1 5 1 1
[10,] 1 2 3 1 2 1
[11,] 1 1 4 1 2 1
[12,] 1 2 2 2 2 1
[13,] 1 1 3 2 2 1
[14,] 1 2 1 3 2 1
[15,] 1 1 2 3 2 1
[16,] 1 1 1 4 2 1
[17,] 1 2 2 1 3 1
[18,] 1 1 3 1 3 1
[19,] 1 2 1 2 3 1
[20,] 1 1 2 2 3 1
[21,] 1 1 1 3 3 1
[22,] 1 2 1 1 4 1
[23,] 1 1 2 1 4 1
[24,] 1 1 1 2 4 1
[25,] 1 1 1 1 5 1
[26,] 1 2 3 1 1 2
[27,] 1 1 4 1 1 2
[28,] 1 2 2 2 1 2
[29,] 1 1 3 2 1 2
[30,] 1 2 1 3 1 2
[31,] 1 1 2 3 1 2
[32,] 1 1 1 4 1 2
[33,] 1 2 2 1 2 2
[34,] 1 1 3 1 2 2
[35,] 1 2 1 2 2 2
[36,] 1 1 2 2 2 2
[37,] 1 1 1 3 2 2
[38,] 1 2 1 1 3 2
[39,] 1 1 2 1 3 2
[40,] 1 1 1 2 3 2
[41,] 1 1 1 1 4 2
[42,] 1 2 2 1 1 3
[43,] 1 1 3 1 1 3
[44,] 1 2 1 2 1 3
[45,] 1 1 2 2 1 3
[46,] 1 1 1 3 1 3
[47,] 1 2 1 1 2 3
[48,] 1 1 2 1 2 3
[49,] 1 1 1 2 2 3
[50,] 1 1 1 1 3 3
[51,] 1 2 1 1 1 4
[52,] 1 1 2 1 1 4
[53,] 1 1 1 2 1 4
[54,] 1 1 1 1 2 4
[55,] 1 1 1 1 1 5

Answer 2

limits = c(1,2,5,6,7,6)
mysum = 10

set.seed(42)
ans = setNames(limits, paste0("x", 1:length(limits)))
while(sum(ans) > mysum){
    ind = sample(which(ans > 1), 1)
    ans[ind] = ans[ind] - 1
}

ans
#x1 x2 x3 x4 x5 x6 
# 1  1  4  2  1  1 

sum(ans)
#[1] 10