Algorithm: Calculate every number in a given list using addition and numbers you've created

Question

I'm creating an algorithm to calculate every number in an array using only addition and numbers we've created - in the shortest amount of steps. That's confusing so here is an example:

input: [5, 11], used numbers (start with 1): [1]
1+1=2, used: [1, 2]
2+2=4, used: [1, 2, 4]
1+4=5, [1, 2, 4, 5]
5+5=10, [1, 2, 4, 5, 10]
10+1=11, [1, 2, 4, 5, 10, 11]

We have hit 5 and 11 so we are done in 5 steps. There are other ways to get [5, 11], eg. [1, 2, 3, 5, 6, 11]. They are the same amount of steps. Imagine we have input [5, 11, 20]. Now it matters which we choose above because [1, 2, 4, 5, 10, 11] only requires one more step, 10+10.

The input can be hundreds of numbers. Certainly I can't attempt every possibility. I was thinking about an "elegant" solution using prime factors. If my input is [16, 30, 36, 40], does it help me to think about this as [2*2*2*2, 2*3*5, 2*2*3*3, 2*2*2*5]? I'm not sure. I've also thought about using the differences of each input, eg. [16, 30, 36, 40] would give me [14, 6, 4, 20, 24, 10], but I'm not sure how to use that either.

Any thoughts?

Answer 1

It's NP complete, but you may have a chance in many practical cases, especially if you need to produce a lot of numbers in a not very large range. I'll call the numbers you want to produce "desired numbers", and assume that 1 is not one of the "desired numbers".

An important observation is that in any chain, performing an addition that produces one of the desired numbers is optimal. Therefore, we need only count the additions that don't produce one of the desired numbers (and if you want to produce 100 numbers from 1 to 200 those additions might be very few).

So instead of the initial set { 1 }, we add { 2 } if it is one of the desired numbers, then add 3 or 4 if they are among the desired numbers, and so on. If you wanted { 2, 3, 5, 6, 10, 19, 20, 21, 50 } then you start with the initial set { 1, 2 = 1+1, 3 = 2+1, 5 = 3+2, 6 = 5+1, 10 = 5+5, 20 = 10+10, 21 = 20+1 } and you only need to find 19 and 50.

Then each move consists of adding the sum of two numbers, and then adding all of the desired numbers that can now be produced. In the example, one move would be adding 16 and 19, another move adding 40 and 50. All this really cuts down on the number of possibilities you need to try out.

Some more ways to cut down on the possibilities: We can require that the non-desired numbers are produced in increasing order. So if you produced 2 and 4, you cannot produce the number 3 anymore. Or if you produced 2, 3, 5, you cannot produce the number 4 anymore - if you wanted it, you should have produced it earlier.

Obviously you don't ever produce a number larger than the highest desired number. Or higher than the highest desired number that wasn't produced yet. And all numbers greater than the highest desired number that wasn't produced yet must have been used producing one of the higher desired numbers.

And you cannot ever produce a number larger than the smallest desired number not found yet.

Apart from that, I cannot think of any "elegant" algorithm. I'd try all the possibilities, producing large numbers first, and of course stopping when you can prove you are not going to find a solution than the best so far.

Your example: [16, 30, 36, 40].

First attempt, always adding the largest number possible according to the rules: 2, 4, 8+16, 24, 28+30, 34+36+40. That's six moves, so you can try to find a better solution using five or fewer moves using backtracking. (Note that in move 4 and 5 we couldn't produce a number > 30 according to the rules).

Producing 26 or 25 in step 5 doesn't help. In step 4, we could produce 20+36+40, 18+36+40, 17, 12, 10, 9. 20+36+40 can be followed by 28+30, so we found a better solution using five moves only (2, 4, 8+16, 20+36+40, 28+30). Now the goal is to find a chain with four or fewer extra additions.

2, 4, 8+16 doesn't give success with four extra additions. We can try 2, 4, 6 or 2, 4, 5 or 2, 3, 6 or 2, 3, 5 or 2, 3, 4 which all don't solve the problem in four moves. So (2, 4, 8+16, 20+36+40, 28+30) with five moves plus four moves adding the four desired numbers is an optimal solution.

Answer 2

You're looking for an algorithm to generate an addition chain that includes each of the specified numbers. As Wikipedia explains, the problem is NP-complete in general. However, there are approximation algorithms and heuristics. Searching for algorithms for computing addition chains should give you some candidate methods.

Answer 3

This is the addition sequence problem. You can transform the addition sequence problem into the vector addition chain problem as well. The best known algorithm for computing these is:

D. Bleichenbacher and A. Flammenkamp "An Efficient Algorithm for Computing Shortest Addition Chains"

This is unpublished but you can find it on the addition chain website:

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

You essentially need to write a function what will approximate (find a lower bound) the size of an addition sequence. For this I use the bounding sequences in this paper:

E. G. Thurber "Efficient Generation of Minimal Length Addition Chains", SIAM Journal of Computing, V. 28(4) 1999 pp 1247-1263.

Myself and Ed have an update to this paper with better bounds. Now you work in reverse with the algorithm of Flammenkamp etc by removing the largest element in the set and splitting it as per the paper. You then prune with known l(n) values that I have already calculated as well as using your lower bound for the addition sequence that is updated with the split values. You will need to understand the graph representation of addition chains to understand this algorithm. I have numerous unpublished updates to this algorithm in the code that I use. This is quite old work of mine as there are better approaches for the single number addition chain problem I study.