       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:= getSolutions[20, 20, 2]

Out= {{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:= Timing[sols = getSolutions[20, 20, 4];]
Out= {0.042993, Null}

In:= Length[sols]
Out= 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:= numberOfSolutions[sum_, max_, n_] := Module[
{x, poly},
poly = Total[x^Range[0, max]];
Coefficient[poly^n, x^sum]]

In:= numberOfSolutions[20, 20, 4]
Out= 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