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: [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


  • Prev by Date: Re: SetOptions does not work with Grid
  • Next by Date: Re: minimax polynomial determination
  • Previous by thread: Re: Simple n-tuple problem - with no simple solution
  • Next by thread: Re: Simple n-tuple problem - with no simple solution