6
$\begingroup$

I have a list $X=\{n_1,n_2,n_3,n_4, \dots, n_i\}$ with $n_i \in \mathbb{C}$, an integer $m \in \mathbb{N}$ and $S \in \mathbb{C}$. My question is how to find all solution to the equation

$$\sum_{j=1}^m x_j=S $$ in an efficient way with Mathematica?

An example:

X={1,1/2,0,-1/2,-1};
m=3;
S=1;

I want a function combinations[X,m,S] which returns

combinations[X,m,S]
{{1,3,3},{3,1,3},{3,3,1},{1,2,4},{1,4,2},{2,1,4},{4,1,2},{2,4,1},{4,2,1},{1,1,5},{1,5,1},{5,1,1},{2,2,3},{2,3,2},{3,2,2}}

where each triple gives the index to X. For example, {1,3,3} stands for

$$S=x_1+x_3+x_3=1+0+0=1.$$

The solution I have is very slow and takes a lot of memory: I perform m tensor-products of $X$, creating a $M=i \otimes i \otimes \dots \otimes i$ matrix (with dimension of $d(M)=i^m$, and sum each entry. Unfortunatly, the matrix M grows exponentially, and is unfeasible even for small $m$ below 20.

So let me two ask:

1) Do you know a more efficient solution for finding all solutions of the equation above?

2) Do you know a more efficient solution for finding all solutions of the equation above, for the special cases of $S=0$ and $S=1$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This isn't exactly the subset sum problem, but dynamic programming seems like the answer. $\endgroup$
    – lirtosiast
    Commented Jul 21, 2019 at 16:40
  • 2
    $\begingroup$ IntegerPartitions[S, {m}, X] and post-process (Permutations)? $\endgroup$
    – kglr
    Commented Jul 21, 2019 at 16:44
  • 1
    $\begingroup$ @kglr wow I was trying IntegerPartitions before and couldnt get it work, i didnt know about the third argument. It works for rational numbers, that is already really cool, thanks! Could this be extended to complex values? (at least for question 2?) Thaanks!! $\endgroup$
    – Mario Krenn
    Commented Jul 21, 2019 at 16:52

2 Answers 2

Reset to default
5
$\begingroup$

For rational $n_i$ and $S$, you can use IntegerPartitions:

X = {1, 1/2, 0, -1/2, -1};
m = 3;
S = 1;

posIndex=PositionIndex[X];

Flatten /@ Map[posIndex, Join @@ (Permutations /@ IntegerPartitions[S, {m}, X]), {-1}]

{{5, 1, 1}, {1, 5, 1}, {1, 1, 5}, {4, 2, 1}, {4, 1, 2}, {2, 4, 1}, {2,1, 4}, {1, 4, 2}, {1, 2, 4}, {3, 3, 1}, {3, 1, 3}, {1, 3, 3}, {3, 2, 2}, {2, 3, 2}, {2, 2, 3}}

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Very beautiful application of IntegerPartitions. As complex numbers can be interpreted as 2dimensional real numbers, would it be possible to modify your code to also cover complex rational X and S? Thanks! $\endgroup$
    – Mario Krenn
    Commented Jul 21, 2019 at 17:11
  • 2
    $\begingroup$ Thank you @NicoDean. For complex X and S with rational real and imaginary parts, I think we can use MapThread[IntegerPartitions[#, {m},#2]& , {ReIm @ S,Transpose[ReIm @ X]}] to get the core part. Of course, because we are using Permutations m has to be small. $\endgroup$
    – kglr
    Commented Jul 21, 2019 at 17:28
  • $\begingroup$ I think I understand what you try to do with ReIm. I tried now for some time but unfortunatly I cannot get it running. So in case that it is clear for you how to continue from there, could you maybe give some more hints? Otherwise i will try further myself. Thanks $\endgroup$
    – Mario Krenn
    Commented Jul 21, 2019 at 18:54
  • $\begingroup$ @NicoDean, sorry --- we need to change Transpose[ReIm @ X] to se[ReIm/ @ X] (or better to ReIm@X). $\endgroup$
    – kglr
    Commented Jul 21, 2019 at 19:37
5
$\begingroup$

Could use Solve.

The example in question:

xvals = {1, 1/2, 0, -1/2, -1};
m = 3;
ss = 1;

Set up the equations and inequalities that need to be enforced.

vars = Array[n, Length[xvals]];
constraints = 
  Flatten[{Total[vars] - m == 0, vars.xvals - ss == 0, 
    Thread[vars >= 0]}];
Solve[constraints, vars, Integers]

(* Out[221]= {{n[1] -> 0, n[2] -> 2, n[3] -> 1, n[4] -> 0, 
  n[5] -> 0}, {n[1] -> 1, n[2] -> 0, n[3] -> 2, n[4] -> 0, 
  n[5] -> 0}, {n[1] -> 1, n[2] -> 1, n[3] -> 0, n[4] -> 1, 
  n[5] -> 0}, {n[1] -> 2, n[2] -> 0, n[3] -> 0, n[4] -> 0, n[5] -> 1}} *)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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