Re: Simple n-tuple problem - with no simple solution
- To: mathgroup at smc.vnet.net
- Subject: [mg115797] Re: Simple n-tuple problem - with no simple solution
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Fri, 21 Jan 2011 04:30:19 -0500 (EST)
Don wrote:
> Problem: Given an n-tuple (n >= 1). with each element able to take
> on the values in
> Range[0, 1.0, .05] , produce all the n-tuples that sum to 1.0.
>
> The most direct way to solve this problem is to generaate all possible
> n-tuples and Select out all those that sum to 1.0.
>
> For example, when n = 2 :
>
> n = 2;
> Select[Tuples[Table[Range[0, 1.0, .05], {n}]], Total[#] == 1 &]
>
> The problem with this solution is that the number of n-tuples that are
> generated before the Select is used grows exponentially fast as a
> function
> of n - causing the system to run out of memory (RAM) very quickly.
>
> Is there a more memory efficient way to solve this problem that
> doesn't
> use so much memory but still is not too slow in terms of processor
> time?
>
> Thank you.
I'm sure there are better ways to code this, but here is one approach. I
will work with integers, so I would have 20 and 1 where you have 1 and
.05 respectively.
getSolutions[sum_, max_, 1] := If[max < sum, {}, {{sum}}]
getSolutions[sum_, max_, n_] := Module[
{subsols},
Union[Flatten[Table[
subsols = getSolutions[j, max, n - 1];
If[Length[subsols] >= 1,
Table[
Insert[subsols[[i]], sum - j, k], {k, 1, n},
{i, Length[subsols]}]
, {}]
, {j, Max[sum - max, 0], sum}], 2]]
]
Example:
In[280]:= getSolutions[20, 20, 2]
Out[280]= {{0, 20}, {1, 19}, {2, 18}, {3, 17}, {4, 16}, {5, 15}, {6,
14}, {7, 13}, {8, 12}, {9, 11}, {10, 10}, {11, 9}, {12, 8}, {13,
7}, {14, 6}, {15, 5}, {16, 4}, {17, 3}, {18, 2}, {19, 1}, {20, 0}}
This code is not too slow.
In[277]:= Timing[sols = getSolutions[20, 20, 4];]
Out[277]= {0.042993, Null}
In[278]:= Length[sols]
Out[278]= 1771
Probably could be made faster either via Compile or a smarter algorithm.
Note that if you were only interested in teh number of possibilities,
that's easier to obtain.
In[229]:= numberOfSolutions[sum_, max_, n_] := Module[
{x, poly},
poly = Total[x^Range[0, max]];
Coefficient[poly^n, x^sum]]
In[279]:= numberOfSolutions[20, 20, 4]
Out[279]= 1771
One caveat is that I have not tried to test this extensively. So there
might be edge cases that misbehave.
Daniel Lichtblau
Wolfram Research