5
$\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$?

$\endgroup$
  • 1
    $\begingroup$ This isn't exactly the subset sum problem, but dynamic programming seems like the answer. $\endgroup$ – lirtosiast Jul 21 '19 at 16:40
  • 2
    $\begingroup$ IntegerPartitions[S, {m}, X] and post-process (Permutations)? $\endgroup$ – kglr Jul 21 '19 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 Jul 21 '19 at 16:52
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}}

$\endgroup$
  • 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 Jul 21 '19 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 Jul 21 '19 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 Jul 21 '19 at 18:54
  • $\begingroup$ @NicoDean, sorry --- we need to change Transpose[ReIm @ X] to se[ReIm/ @ X] (or better to ReIm@X). $\endgroup$ – kglr Jul 21 '19 at 19:37
4
$\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}} *)
$\endgroup$

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.