Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: New Mathematica file format .cdf; what is it?
  • Next by Date: Re: Mathematica 8 browser plugin and Firefox 3/4
  • Previous by thread: Re: Simple n-tuple problem - with no simple solution
  • Next by thread: Re: Simple n-tuple problem - with no simple solution