Re: Simple n-tuple problem - with no simple solution
- To: mathgroup at smc.vnet.net
- Subject: [mg115801] Re: Simple n-tuple problem - with no simple solution
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Fri, 21 Jan 2011 04:31:06 -0500 (EST)
One natural way is to write a program using an algorithm known as backtrack ing. It's not very hard but it requires careful procedural programming (at least I don't know of any other way to write such a program) and I really don't have the time to spend on this. So instead, I will demonstrate how to do this using a package function that does it automatically. But there is a caveat: the package function is pretty inefficient. One can write vastly more efficient "custom" backtracking programs and even compile them to C (in Mathematica 8) to get probably quite impressive performance. But here I am only interested in a "proof of concept" so here it is.
We first load the old Combinatorica package, which is now at least partly obsolete:
<< Combinatorica`
(ignore the messages).
O.K. let's first take some not too large n:
n = 5;
We now define our "space" over which the backtracking will be done:
sp = Table[Range[0, 1.0, .05], {n}];
Next, we need a test for what constitutes a partial solution. The test simply checks if the sum of the elements of an n-tuple is less or equal to 1.
partialQ[p_] := Total[p] <= 1
Next, we need another test which checks if we have a genuine solution. It checks if the sum of the elements is precisely 1:
finalQ[p_] := Total[p] == 1
Now we run the function Backtrack. We want to use the last argument All, which is needed to get all solutions. Mathematica shows syntax error claiming that the function only takes 3 arguments - but this is not true and the program works fine:
In[6]:= sols = Backtrack[sp, partialQ, finalQ, All]; // Timing
Out[6]= {8.25842,Null}
Let's see how many solutions we have found:
In[7]:= Length[sols]
Out[7]= 10626
Quite many. Let's see some of them:
In[8]:= Take[sols, 20]
(0. 0. 0. 0. 1.
0. 0. 0. 0.05 0.95
0. 0. 0. 0.1 0.9
0. 0. 0. 0.15 0.85
0. 0. 0. 0.2 0.8
0. 0. 0. 0.25 0.75
0. 0. 0. 0.3 0.7
0. 0. 0. 0.35 0.65
0. 0. 0. 0.4 0.6
0. 0. 0. 0.45 0.55
0. 0. 0. 0.5 0.5
0. 0. 0. 0.55 0.45
0. 0. 0. 0.6 0.4
0. 0. 0. 0.65 0.35
0. 0. 0. 0.7 0.3
0. 0. 0. 0.75 0.25
0. 0. 0. 0.8 0.2
0. 0. 0. 0.85 0.15
0. 0. 0. 0.9 0.1
0. 0. 0. 0.95 0.05
)
Andrzej Kozlowski
On 20 Jan 2011, at 12:33, 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.
>