Select rows where sum of a column equals a fixed value in R

Question

I would like to get one (or all) possible combination of rows where sum of quantity column equals 20

here an example :

structure(list(id = 1:10, quantity = c(11L, 1L, 4L, 12L, 19L, 10L, 3L, 13L, 16L, 14L)), class ="data.frame", row.names = c(NA,-10L))

id quantity
1   11          
2   1           
3   4           
4   12          
5   19          
6   10          
7   3           
8   13          
9   16          
10  14

desired output (one possible set) :

id quantity
3   4           
7   3           
8   13

or

id quantity
 2  1           
 5  19

No fixed rule, i just need any combination that satistfies sum(quantity)==20 — Seif, May 13 '20 at 09:26
See [this](https://stackoverflow.com/questions/30858688/find-all-combinations-of-numbers-that-sum-to-a-target) and [this](https://stackoverflow.com/questions/30905044/finding-all-combinations-of-four-numbers-that-equal-a-sum-in-r?noredirect=1&lq=1) — NelsonGon, May 13 '20 at 09:32

GKi · Answer 1 · 2020-05-13T09:37:59.117

In case the combination are ok:

target <- 20
lapply(seq_len(sum(cumsum(sort(x$quantity)) <= target)), function(n) {
  y <- combn(x$quantity, n)
  y[,colSums(y) == target]
})
#[[1]]
#integer(0)
#
#[[2]]
#     [,1] [,2]
#[1,]    1    4
#[2,]   19   16
#
#[[3]]
#     [,1] [,2]
#[1,]    1    4
#[2,]    3    3
#[3,]   16   13
#
#[[4]]
#[1]  1  4 12  3

...and to get the row:

lapply(seq_len(sum(cumsum(sort(x$quantity)) <= target)), function(n) {
  y <- combn(x$quantity, n)
  y <- y[,colSums(y) == target, drop = FALSE]
  if(length(y) > 0) {apply(y, 2, match, x$quantity)}
})
#[[1]]
#NULL
#
#[[2]]
#     [,1] [,2]
#[1,]    2    3
#[2,]    5    9
#
#[[3]]
#     [,1] [,2]
#[1,]    2    3
#[2,]    7    7
#[3,]    9    8
#
#[[4]]
#     [,1]
#[1,]    2
#[2,]    3
#[3,]    4
#[4,]    7

... and somehow like the expected output:

lapply(seq_len(sum(cumsum(sort(x$quantity)) <= target)), function(n) {
  y <- combn(x$quantity, n)
  y <- y[,colSums(y) == target, drop = FALSE]
  if(length(y) > 0) {apply(y, 2, function(i) {x[match(i, x$quantity),]})}
})
#[[1]]
#NULL
#
#[[2]]
#[[2]][[1]]
#  id quantity
#2  2        1
#5  5       19
#
#[[2]][[2]]
#  id quantity
#3  3        4
#9  9       16
#
#
#[[3]]
#[[3]][[1]]
#  id quantity
#2  2        1
#7  7        3
#9  9       16
#
#[[3]][[2]]
#  id quantity
#3  3        4
#7  7        3
#8  8       13
#
#
#[[4]]
#[[4]][[1]]
#  id quantity
#2  2        1
#3  3        4
#4  4       12
#7  7        3

Data:

x <- structure(list(id = 1:10, quantity = c(11L, 1L, 4L, 12L, 19L, 10L, 3L, 13L, 16L
  , 14L)), class ="data.frame", row.names = c(NA,-10L))

I have made an update which returns the rows - as originally asked. — GKi, May 13 '20 at 09:38

ThomasIsCoding · Accepted Answer · 2020-05-14T12:46:20.980

3

Here is another base R solution by defining a recursive function subsetSum (I guess this would be faster since it avoids checking through all combinations)

subsetSum <- function(v, target, r = c()) {
    if (sum(r) == target) {
        return(list(r))
    }
    unlist(lapply(seq_along(v), function(k) subsetSum(v[-(1:k)], target, c(r, v[k]))), recursive = FALSE)
}

Then, when running

target <- 20
lst <- subsetSum(setNames(df$quantity, seq(nrow(df))), target)
res <- Map(function(v) df[as.integer(names(v)), ], lst)

you will get

> res
[[1]]
  id quantity
2  2        1
3  3        4
4  4       12
7  7        3

[[2]]
  id quantity
2  2        1
5  5       19

[[3]]
  id quantity
2  2        1
7  7        3
9  9       16

[[4]]
  id quantity
3  3        4
7  7        3
8  8       13

[[5]]
  id quantity
3  3        4
9  9       16

If you want only one of the subset sum which reaches the given value, you can try subsetsum from package adagio

library(adagio)
target <- 20
res <- df[subsetsum(df$quantity,target)$inds,]

which gives

> res
  id quantity
2  2        1
5  5       19

edited May 14 '20 at 12:46

answered May 13 '20 at 21:23

ThomasIsCoding

96,636
9
24
81

I like your solution, how can i get it to stop looping at the first combination that satisfies the sum condition ? i added a break instruction in the if statement but not working (i have to loop it over 3000 products each having at least quantity array of length of 100) – Seif May 14 '20 at 10:31
2

@Seif I don't think you are able to break into the recursion and extract the first combination. Instead, you can use function `subsetsum` from package `adagio` to make it. See my updates. – ThomasIsCoding May 14 '20 at 12:47
What would happen if no combination sum the target? There is any solution to find the nearest combination to the target? – kikusanchez Nov 15 '22 at 22:47
1

@kikusanchez You can specify your question with an example and post it rather than a comment – ThomasIsCoding Nov 16 '22 at 09:12
Ok @ThomasIsCoding, I'll do it! – kikusanchez Nov 16 '22 at 19:31

Select rows where sum of a column equals a fixed value in R

2 Answers2