2
$\begingroup$

I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays.

I encountered a sub-problem that requires me to break up sums of numbers which are power of 2, i.e. how to find combinations of these numbers that sum up to a certain value. The sum and the combination size are given. Also only 4 power of 2s can be present in a combination: 2,4,8,16.

Lets suppose I have a sum of 8 and I need to break up into a set of 3 numbers. The result would invariably be [2,2,4].

If I need to break up 20 into 3 power of 2s, I could have [2,2,16] or [4,8,8].

Naturally larger sets will result in many possible combinations.

My aim is to write an algorithm that obtains all possible combinations as efficiently as possible. I'm not looking for the algorithm itself, but some leads into how to partition the number. What are some properties of power of 2s that I need to use to partition a sum into a possible combination?

$\endgroup$
  • 1
    $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Apr 15 '14 at 10:17
  • $\begingroup$ In particular, have you checked out the huge theory around partitions of numbers? $\endgroup$ – Raphael Apr 15 '14 at 10:18
  • 1
    $\begingroup$ I modified the question, adding a more direct question in the end. Note this not a homework question, just a problem I came up with when writing a larger algorithm. Thanks for the links. $\endgroup$ – user16784 Apr 15 '14 at 11:00
  • 1
    $\begingroup$ Your comment makes me think that you did not read mine. What have you tried and where did you get stuck? $\endgroup$ – Raphael Apr 15 '14 at 12:01
3
$\begingroup$

Look at the binary representation of the sum. Each 1 in that representation represents a power of two that has to be included as a summand, either directly or indirectly.

If the number of 1s in that representation is greater than the number of summands, there is no solution, if it is equal, there is exactly one solution, and if it is smaller, things get interesting.

The basic property you'll want to exploit in the last case is that you can represent any power of two as once that power, or twice the next smaller power, or 4 times the one after that and so on.

I think this approach can lead to an efficient algorithm. (But I did not follow it through myself, so no guarantees.)

$\endgroup$
1
$\begingroup$

First, note that there could be exponentially (in input length) many such partitions. For example, consider $$ 4 + 4^2 + \cdots + 4^{2n}. $$ There are at least $\binom{2n}{n} = \Theta(4^n/\sqrt{n})$ such partitions with $3n$ parts.

Here is a naive algorithm which should be quite efficient. Suppose we want to split $n$ into $k$ parts. Write $n = 2a + b$, where $b \in \{0,1\}$, and let $\ell$ be the number of 1's in the binary representation of $a$. For $\max(0,k-b-a)/2 \leq t \leq (k-\ell-b)/2$, compute all representations of $a-t$ with $k-b-2t-a$ parts (recursively), multiply them by 2 and add $2t+b$ copies of 1. We have chosen the bounds on $t$ so that for every choice of $t$ there is at least one representation of $a-t$ with $k-b-2t-a$ parts.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy