0
$\begingroup$

Is there a way to determine if a partition of integer $n$ into a given set of integers (represented by a vector $\mathbf{x}$) exists, other than enumerating all partitions of $n$ and checking if one matches $\mathbf{x}$?

For instance, I have $\mathbf{x} = (3, 7)$ and I want to know if $1000$ can be written as a sum $\sum_{i=1} \mathbf{x}_i \cdot \mathbf{k}_i$, where $\mathbf{k}_i$ are the multiplicities of the parts.

I'm not really interested in finding the number of those partitions or enumerating them all. I'm only interested to find if one exists. I was unable to find any literature on this at all.

So far, I only came up with $0 \ge \mathbf{k}_i \ge \lfloor \frac{n}{\mathbf{x}_i} \rfloor$ and I'm just enumerating all possible combinations of $\mathbf{k}_i$ for $i \ge 2$ until I find / do not find one that sums up to $n - m \cdot \mathbf{x}_1$ with $m$ being a positive integer (can test for that quickly by dividing $n - \sum_{i=2} \mathbf{x}_i \cdot \mathbf{k}_i$ by $\mathbf{x}_1$ and checking if there is a remainder ... that saves me some combinations). It works for reasonably small numbers but it is not horribly elegant.

$\endgroup$
2
$\begingroup$

This is the coin problem. If your vector is of length $2$, there is a good solution. If the values are coprime, the largest number that cannot be represented is $x_1x_2-x_1-x_2$. If they are not coprime, your target must be divisible by the $\gcd$, then divide the target and the values by that $\gcd$. For longer vectors it is not easy.

$\endgroup$
  • $\begingroup$ Oh, thanks. Now I feel stupid that I missed that. Somehow the coin problem is not linked from the partition page on Wikipedia. $\endgroup$ – the swine Aug 11 '16 at 13:55
  • $\begingroup$ The partition problem usually considers various sizes of parts, so is rather different. $\endgroup$ – Ross Millikan Aug 11 '16 at 14:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.