Re: Simple n-tuple problem - with no simple solution

*To*: mathgroup at smc.vnet.net*Subject*: [mg115824] Re: Simple n-tuple problem - with no simple solution*From*: Peter Pein <petsie at dordos.net>*Date*: Fri, 21 Jan 2011 04:35:34 -0500 (EST)*References*: <ih96hc$oup$1@smc.vnet.net>

On 20.01.2011 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. > Hi Don, I have not been patient enough to compare for 5-tuples; so here are the times and memory usages for 4-tuples: In[1]:= m0 = MemoryInUse[]; AbsoluteTiming[ Length[p4a = With[{n = 4}, 0.05 Flatten[ Permutations /@ (PadRight[#1, n] &) /@ IntegerPartitions[20, n], 1]]]] m1 = MemoryInUse[]; Print["~", m1 - m0, " bytes"] Out[2]= {0.0120005, 1771} During evaluation of In[1]:= ~136744 bytes In[5]:= AbsoluteTiming[ Length[p4b = Select[Tuples[Range[0, 1, .05], {4}], Plus @@ #1 == 1 &]]] m2 = MemoryInUse[]; Print["~", m2 - m1, " bytes"] Out[5]= {3.1201282, 1771} During evaluation of In[5]:= ~324072 bytes In[8]:= Sort[p4a] == p4b Out[8]= True and for n=9 (the largest case my laptop can handle with this algorithm) I get the result {20.7098512, 3108105} (seconds, number of 9-tuples). Cheers, Peter