Finding all possible combinations of numbers to reach a given sum
This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print "sum(%s)=%s" % (partial, target)
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
subset_sum(remaining, target, partial + [n])
if __name__ == "__main__":
subset_sum([3,9,8,4,5,7,10],15)
#Outputs:
#sum([3, 8, 4])=15
#sum([3, 5, 7])=15
#sum([8, 7])=15
#sum([5, 10])=15
This type of algorithms are very well explained in the following Stanford's Abstract Programming lecture - this video is very recommendable to understand how recursion works to generate permutations of solutions.
Edit
The above as a generator function, making it a bit more useful. Requires Python 3.3+ because of yield from.
def subset_sum(numbers, target, partial=[], partial_sum=0):
if partial_sum == target:
yield partial
if partial_sum >= target:
return
for i, n in enumerate(numbers):
remaining = numbers[i + 1:]
yield from subset_sum(remaining, target, partial + [n], partial_sum + n)
Here is the Java version of the same algorithm:
package tmp;
import java.util.ArrayList;
import java.util.Arrays;
class SumSet {
static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
int s = 0;
for (int x: partial) s += x;
if (s == target)
System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
if (s >= target)
return;
for(int i=0;i<numbers.size();i++) {
ArrayList<Integer> remaining = new ArrayList<Integer>();
int n = numbers.get(i);
for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
partial_rec.add(n);
sum_up_recursive(remaining,target,partial_rec);
}
}
static void sum_up(ArrayList<Integer> numbers, int target) {
sum_up_recursive(numbers,target,new ArrayList<Integer>());
}
public static void main(String args[]) {
Integer[] numbers = {3,9,8,4,5,7,10};
int target = 15;
sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
}
}
It is exactly the same heuristic. My Java is a bit rusty but I think is easy to understand.
C# conversion of Java solution: (by @JeremyThompson)
public static void Main(string[] args)
{
List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
int target = 15;
sum_up(numbers, target);
}
private static void sum_up(List<int> numbers, int target)
{
sum_up_recursive(numbers, target, new List<int>());
}
private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
int s = 0;
foreach (int x in partial) s += x;
if (s == target)
Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);
if (s >= target)
return;
for (int i = 0; i < numbers.Count; i++)
{
List<int> remaining = new List<int>();
int n = numbers[i];
for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
List<int> partial_rec = new List<int>(partial);
partial_rec.Add(n);
sum_up_recursive(remaining, target, partial_rec);
}
}
Ruby solution: (by @emaillenin)
def subset_sum(numbers, target, partial=[])
s = partial.inject 0, :+
# check if the partial sum is equals to target
puts "sum(#{partial})=#{target}" if s == target
return if s >= target # if we reach the number why bother to continue
(0..(numbers.length - 1)).each do |i|
n = numbers[i]
remaining = numbers.drop(i+1)
subset_sum(remaining, target, partial + [n])
end
end
subset_sum([3,9,8,4,5,7,10],15)
Edit: complexity discussion
As others mention this is an NP-hard problem. It can be solved in exponential time O(2^n), for instance for n=10 there will be 1024 possible solutions. If the targets you are trying to reach are in a low range then this algorithm works. So for instance:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generates 1024 branches because the target never gets to filter out possible solutions.
On the other hand subset_sum([1,2,3,4,5,6,7,8,9,10],10) generates only 175 branches, because the target to reach 10 gets to filter out many combinations.
If N and Target are big numbers one should move into an approximate version of the solution.
All possible combinations of a set that sum to a target value
Finding any subset of a set of integers that sums to some target t is a form of the subset sum problem, which is NP-complete. As a result, efficiently computing all the combinations (repeats allowed) of your set that sum to a target value is theoretically challenging.
To tractably solve a special case of the subset sum problem, let's recast your problem by assuming the input is positive integers (for your example w <- c(2, 4, 6, 8, 10); I won't consider non-positive integers or non-integers in this answer) and that the target is also a positive integer (in your example 10). Define D(i, j) to be the set of all combinations that sum to i among the first j elements of the set w. If there are n elements in w, then you are interested in D(t, n).
Let's start with a few base cases: D(0, k) = {{}} for all k >= 0 (the only way to sum to 0 is to include none of the elements) and D(k, 0) = {} for any k > 0 (you can't sum to a positive number with zero elements). Now consider the following pseudocode to compute arbitrary D(i, j) values:
for j = 1 ... n
for i = 1 ... t
D[(i, j)] = {}
for rep = 0 ... floor(i/w_j)
Dnew = D[(i-rep*w_j, j-1)], with w_j added "rep" times
D[(i, j)] = Union(D[(i, j)], Dnew)
Note that this could still be quite inefficient (D(t, n) can contain an exponentially large number of feasible subsets so there is no avoiding this), but in many cases where there are a relatively small number of feasible combinations that sum to the target this could be quite a bit quicker than simply considering every single subset of the set (there are 2^n such subsets, so that approach always has exponential runtime).
Let's use R to code up your example:
w <- c(2, 4, 6, 8, 10)
n <- length(w)
t <- 10
D <- list()
for (j in 0:n) D[[paste(0, j)]] <- list(c())
for (i in 1:t) D[[paste(i, 0)]] <- list()
for (j in 1:n) {
for (i in 1:t) {
D[[paste(i, j)]] <- do.call(c, lapply(0:floor(i/w[j]), function(r) {
lapply(D[[paste(i-r*w[j], j-1)]], function(x) c(x, rep(w[j], r)))
}))
}
}
D[[paste(t, n)]]
# [[1]]
# [1] 2 2 2 2 2
#
# [[2]]
# [1] 2 2 2 4
#
# [[3]]
# [1] 2 4 4
#
# [[4]]
# [1] 2 2 6
#
# [[5]]
# [1] 4 6
#
# [[6]]
# [1] 2 8
#
# [[7]]
# [1] 10
The code correctly identifies all combinations of elements in the set that sum to 10.
To efficiently get all 2002 unique length-10 combinations, we can use the allPerm function from the multicool package:
library(multicool)
out <- do.call(rbind, lapply(D[[paste(t, n)]], function(x) {
allPerm(initMC(c(x, rep(0, 10-length(x)))))
}))
dim(out)
# [1] 2002 10
head(out)
# [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,] 2 2 2 2 2 0 0 0 0 0
# [2,] 0 2 2 2 2 2 0 0 0 0
# [3,] 2 0 2 2 2 2 0 0 0 0
# [4,] 2 2 0 2 2 2 0 0 0 0
# [5,] 2 2 2 0 2 2 0 0 0 0
# [6,] 2 2 2 2 0 2 0 0 0 0
For the given input, the whole operation is pretty quick (0.03 seconds on my computer) and doesn't use a huge amount of memory. Meanwhile the solution in the original post ran in 22 seconds and used 15 GB of memory, even when replacing the last line to the (much) more efficient combinations[rowSums(combinations) == 1,].
Finding all possible combinations whose sum is within certain range of target
Instead of allowing multiple values, it would be a lot faster to just compute an integer factor for every value.
For your problem, I get 988 results.
import math
import time
def combinator(tolerance, target, inputs):
# Special case for inputs with one element, speeds up computation a lot
if len(inputs) == 1:
number = inputs[0]
result_min = int(math.ceil((target-tolerance)/number))
result_max = int(math.floor((target+tolerance)/number))
for factor in range(result_min, result_max+1):
yield [factor]
return
# Special case for no inputs, just to prevent infinite recursion
if not inputs:
return
number = inputs[-1]
max_value = int(math.floor((target + tolerance)/number))
for i in range(max_value+1):
for sub_factors in combinator(tolerance, target-i*number, inputs[:-1]):
sub_factors.append(i)
yield sub_factors
def main():
inputs = [18.01, 42.01, 132.04, 162.05, 203.08, 176.03]
target = 1800.71
tolerance = 0.5
t_start = time.perf_counter()
results = list(combinator(tolerance, target, inputs))
t_end = time.perf_counter()
for result in results:
result_str = ""
result_value = 0
for factor, value in zip(result, inputs):
if not factor:
continue
if result_str != "":
result_str += " + "
result_str += "{}* {}".format(factor, value)
result_value += factor*value
print("{:.2f}".format(result_value) + " =\t[" + result_str + "]")
print("{} results found!".format(len(results)))
print("Took {:.2f} milliseconds.".format((t_end-t_start)*1000))
if __name__ == "__main__":
main()
1801.00 = [100* 18.01]
1800.96 = [93* 18.01 + 3* 42.01]
1800.92 = [86* 18.01 + 6* 42.01]
...
1800.35 = [5* 18.01 + 3* 42.01 + 9* 176.03]
1800.33 = [2* 42.01 + 1* 132.04 + 9* 176.03]
1800.35 = [3* 18.01 + 1* 162.05 + 9* 176.03]
988 results found!
Took 11.48 milliseconds.
I also reimplemented the same algorithm in Rust.
Performance on your problem:
- Python: ~12 ms
- Rust: ~0.7 ms
Here is the code:
use std::time::Instant;
fn combinator(tolerance : f32, target: f32, inputs: &[f32]) -> Vec<Vec<i32>>{
let number = match inputs.last() {
Some(i) => i,
None => return vec![]
};
if inputs.len() == 1 {
let result_min = ((target-tolerance)/number).ceil() as i32;
let result_max = ((target+tolerance)/number).floor() as i32;
return (result_min..=result_max).map(|x| vec![x]).collect();
}
let max_value = ((target + tolerance)/number).floor() as i32;
let mut results = vec![];
for i in 0..=max_value {
for mut sub_factors in combinator(tolerance, target - i as f32 * number, &inputs[..inputs.len()-1]) {
sub_factors.push(i);
results.push(sub_factors);
}
}
results
}
fn print_result(factors: &[i32], values: &[f32]){
let sum : f32 = factors.iter()
.zip(values.iter())
.map(|(factor,value)| *factor as f32 * *value)
.sum();
println!("{:.2} =\t[{}]", sum,
factors.iter()
.zip(values.iter())
.filter(|(factor, _value)| **factor > 0)
.map(|(factor, value)| format!("{}* {}", factor, value))
.collect::<Vec<String>>()
.join(", "));
}
fn main() {
let inputs = vec![18.01, 42.01, 132.04, 162.05, 203.08, 176.03];
let target = 1800.71;
let tolerance = 0.5;
let t_start = Instant::now();
let results = combinator(tolerance, target, &inputs);
let duration = t_start.elapsed().as_micros() as f64;
for result in &results {
print_result(&result, &inputs);
}
println!("{} results found!", results.len());
println!("Took {} milliseconds", duration / 1000.0);
}
1801.00 = [100* 18.01]
1800.96 = [93* 18.01, 3* 42.01]
1800.92 = [86* 18.01, 6* 42.01]
...
1800.35 = [5* 18.01, 3* 42.01, 9* 176.03]
1800.33 = [2* 42.01, 1* 132.04, 9* 176.03]
1800.35 = [3* 18.01, 1* 162.05, 9* 176.03]
988 results found!
Took 0.656 milliseconds
Also, just for fun, those are the exact solutions to your problem. There are 5 of them.
1800.71 = [12* 18.01, 1* 42.01, 2* 162.05, 6* 203.08]
1800.71 = [13* 18.01, 2* 42.01, 2* 132.04, 6* 203.08]
1800.71 = [16* 18.01, 7* 42.01, 6* 203.08]
1800.71 = [52* 18.01, 1* 42.01, 1* 132.04, 1* 162.05, 3* 176.03]
1800.71 = [54* 18.01, 4* 42.01, 1* 132.04, 3* 176.03]
Find all combinations of a list of numbers with a given sum
You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn't sum to 10:
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
target = 10
result = [seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]
print(result)
Result:
[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]
Unfortunately this is something like O(2^N) complexity, so it isn't suitable for input lists larger than, say, 20 elements.
Finding all possible combinations of numbers of an array to reach a given sum
Took me while to code this. So it's basically brute force. I recursively (backtracking) generate all possible expression with the operators given and then evaluate them. Note these are just infix expression(s).
Now this is a very slow solution. There are several optimization one can do here.
vector<string> allCombinations(vector<int> &arr, int k)
{
int n = (int)arr.size();
string operators = "+-*";
vector<string> ans;
// To check precedence of operators
auto prec = [&](char op) -> int
{
if (op == '*' or op == '/') return 2;
if (op == '+' or op == '-') return 1;
return -1;
};
// For infix evaluation (kindof a helper function)
auto compute = [&](int v1, char op, int v2) -> int
{
if (op == '+') return v1 + v2;
if (op == '-') return v1 - v2;
if (op == '*') return v1 * v2;
if (op == '/') return v1 / v2;
assert(false);
return INT_MAX;
};
// Main infix evaluation function
auto evaluate = [&](string s) -> int
{
int len = (int)s.size();
// vector is being used as a STACK
vector<int> val;
vector<char> ops;
for (int i = 0; i < len; i++)
{
char curr = s[i];
if (curr == ' ') continue;
if (isdigit(curr))
{
int v = 0;
while (i < len and isdigit(s[i])) v = 10 * v + (s[i++] - '0');
val.push_back(v);
i--;
}
else
{
while (!ops.empty() and prec(curr) <= prec(ops.back()))
{
int v1 = val.back();
val.pop_back();
int v2 = val.back();
val.pop_back();
char op = ops.back();
ops.pop_back();
val.push_back(compute(v2, op, v1));
}
ops.push_back(curr);
}
}
while (!ops.empty())
{
int v1 = val.back();
val.pop_back();
int v2 = val.back();
val.pop_back();
char op = ops.back();
ops.pop_back();
val.push_back(compute(v2, op, v1));
}
return val.back();
};
// Generates all expression possible
function<void(int, string&)> generate = [&](int i, string &s) -> void
{
s += to_string(arr[i]);
if (i == n - 1)
{
if (evaluate(s) == k) ans.push_back(s);
// Backtrack
s.pop_back();
return;
}
for (char &ops : operators)
{
s.push_back(ops);
generate(i + 1, s);
// Backtrack
s.pop_back();
}
// Backtrack
s.pop_back();
};
string s;
// Try all combinations
sort(arr.begin(), arr.end());
do
{
generate(0, s);
} while (next_permutation(arr.begin(), arr.end()));
return ans;
}
Related Topics
Asymmetric Expansion of Ggplot Axis Limits
Two Horizontal Bar Charts with Shared Axis in Ggplot2 (Similar to Population Pyramid)
Coloring Boxplot Outlier Points in Ggplot2
R: What's the How to Overwrite a Function from a Package
Tidyverse - Prefered Way to Turn a Named Vector into a Data.Frame/Tibble
Generate Ggplot2 Boxplot with Different Colours for Multiple Groups
Export Fitted Regression Splines (Constructed by 'Bs' or 'Ns') as Piecewise Polynomials
Passing Arguments to Ggplot in a Wrapper
How to Automatically Create N Lags in a Timeseries
How to Calculate Any Negative Number to the Power of Some Fraction in R
Creating a Vertical Color Gradient for a Geom_Bar Plot
Using Variable Column Names in Dplyr Summarise
How to Expand Axis Asymmetrically with Ggplot2 Without Setting Limits Manually
Reading a CSV File Organized Horizontally
Find All Positions of All Matches of One Vector of Values in Second Vector