Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find all combinations of numbers that sum to a target

Tags:

r

I wish to find the speediest way to find up to 1000 possible combinations of 'n' integers to find a target integer.

For example. Say I wanted to sum to the number '20'. I want to find up to 1000 combinations of four integers that sum to this number. The integers can repeat themselves. I also have a condition that the integer must not be smaller than a particular number, in this case 4.

target<-20  #the number I wish to sum to
lowest<-4   #the smallest integer I allow
size<-4 #the number of integers I wish to use to sum
maxposs <- target - ((size-1) * lowest) #given the lowest, this is the max possible integer. In my example it is 8.

This is how I have started to work this out. Using combn to find all combinations of the four chosen integers and then filtering by those that sum to my target.

m <- combn(rep(lowest:maxposs,size), size)
m1<- m[,colSums(m)==target]

Here, 'm1' has 245 columns. There are only this many solutions. The last few columns:

#     [,238] [,239] [,240] [,241] [,242] [,243] [,244] [,245]
#[1,]      4      4      4      4      4      4      5      5
#[2,]      5      5      5      6      7      4      6      4
#[3,]      7      4      5      4      4      5      4      5
#[4,]      4      7      6      6      5      7      5      6

However, in my real application, I can be dealing with very high integers (summing up to 1000) and want to limit myself to a random sample of 1000 possible combinations. As this is for a randomization statistical test, speed is of the essence. I wonder if anyone knows of a faster way of doing this. My way doesn't feel intuitively quick.

like image 246
jalapic Avatar asked Jun 16 '15 04:06

jalapic


People also ask

How do you find the sum of all combinations?

The sum of all possible combinations of n distinct things is 2 n. C0 + nC1 + nC2 + . . . + nC n = 2 n.

How do you find the sum of all combinations in Python?

First, we take an empty list 'res' and start a loop and traverse each element of the given list of integers. In each iteration, pop the element, store it in 'num', find remaining difference for sum K, and check if the difference exists in the given list or not.

What is combination of sum problem?

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The approach for the problem is simple to find.

How do you find the combination of cells that equal a sum?

Find cells combination that equal a given sum with Solver Add-in. If you are confused with above method, Excel contains a Solver Add-in feature, by using this add-in, you can also identify the numbers which total amount equals a given value.

What is combination sum in Excel?

Combination Sum. Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

What is combination sum in leetcode?

Combination Sum - LeetCode Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times.

What happens if the sum of a combination exceeds the target?

The numbers inside the array and the target are positive integers. Therefore, if the sum of a combination exceeds the value of the target, we no longer need to recurse further with this combination. We need a way so that the duplicate combinations are not generated.

How to find all unique combinations in an array of integers?

Given an array of positive integers arr [] and a sum x, find all unique combinations in arr [] where the sum is equal to x. The same repeated number may be chosen from arr [] unlimited number of times. Elements in a combination (a1, a2, …, ak) must be printed in non-descending order. (ie, a1 <= a2 <= … <= ak).


1 Answers

my_matrix <- matrix(nrow = 1000, ncol = 4)
i <- 1
nn <- 1000
while(i <= 1000){
  x <- sample(x = 4:nn, size = 3)
  y = nn - sum(x)
  if(y >= 4){
    my_matrix[i, ] <- c(x, y)
    i <- i + 1
  }
}

Per Gavin's suggestion, redone with a preallocated matrix. Now this runs in .158 seconds, twice as fast, and probably scales better.

like image 82
goodtimeslim Avatar answered Oct 20 '22 02:10

goodtimeslim