Re: Simple n-tuple problem - with no simple solution
- To: mathgroup at smc.vnet.net
- Subject: [mg115933] Re: Simple n-tuple problem - with no simple solution
- From: Don <donabc at comcast.net>
- Date: Wed, 26 Jan 2011 05:06:07 -0500 (EST)
- References: <ihjjt0$sfv$1@smc.vnet.net>
On Jan 24, 2:22 am, DrMajorBob <btre... at austin.rr.com> wrote:
> Brilliant!
>
> Bobby
>
> On Sun, 23 Jan 2011 16:32:03 -0600, Dana DeLouis <dana.... at gmail.com>
> wrote:
>
>
>
>
>
> > On Jan 22, 3:23 am, DrMajorBob <btre... at austin.rr.com> wrote:
> >> Here are some timings.
>
> >> n = 5; addends = Rationalize@Range[0, 1.0, 0.05];
> >> Length@t1[addends, n] // Timing
>
> >> {1.44372, 192}
> >> {23.6318, 192}
>
> >> n = 7;
> >> Length@t1[addends, n] // Timing
> >> {1.85135, 364}
>
> >> n = 9;
> >> Length@t1[addends, n] // Timing
> >> {2.04216, 488}
>
> >> The Compositions method rendered Mathematica unresponsive at n = 10, but
> >> here's n = 25 for my approach:
> >> n = 25;
> >> Length@t1[addends, n] // Timing
>
> >> {2.57619, 627}
>
> >> I'd say Solve (which must use Integer Linear Programming for this) is
> >> the
> >> way to go.
>
> > Hi. Just some thoughts. With the smallest unit 1, the most n can be
> > is 20.
>
> > If we assume that solution sizes smaller than n have implied 0's, then. ..
>
> > IntegerPartitions[20,5]//Length //Timing
> > {0.000085,192}
>
> > IntegerPartitions[20,20]//Length //Timing
> > {0.000244,627}
>
> > If we want to look at each exact n, then the function uses {n}
>
> > Table[Length[IntegerPartitions[20,{j}]],{j,20}]
> > {1,10,33,64,84,90,82,70,54,42,30,22,15,11,7,5,3,2,1,1}
>
> > Accumulate[%]
> > =
> > {1,11,44,108,192,282,364,434,488,530,560,582,597,608,615,620,623,625,626,62=AD7}
>
> > By adding them up, we see that for n=5, we get the 192. For n=7, 364,
> > etc.
>
> > If the question was "Count all possible combinations" as in the last
> > total above, then one additional way...
>
> > Timing[SeriesCoefficient[
> > 1/Times @@ (1 - n^#1 & ) /@
> > Range[20], {n, 0, 20}]]
>
> > {0.0003, 627}
>
> > = = = = = = = = = =
> > HTH : >)
> > Dana DeLouis
>
> --
> DrMajor... at yahoo.com- Hide quoted text -
>
> - Show quoted text -
Thank you all for the in-depth analysis
of this problem.
The proposed solutions do solve the problem of
memory overflow as opposed to the simple
solution of generating all possible tuples and only then Selecting out
those whose elements sum to 1.
I should add perhaps a little context to the original problem.
It is part of an optimization problem.
All the n-tuples (with the requirement
that all elements of any given tuple add to 1.0 - as explained in
the original problem definition) constitute
essentially the state space
that has to be searched ( in some clever way) to find
the maximum value of an objective function subject
to well defined independent constraints.
The hope was that
the requirement of summing to one would inhibit the
state space from growing too fast for "reasonable"
sizes of n ("reasonable" being about a max of 15 for
the current application). Many of the solutions
proposed show that that is not feasible: the state space
grows very rapidly from about a 5-tuple to larger values of n up to
15.
(A person more knowledgeable than I in combinatorics might have seen
this coming.)
Using the NumberOfCompositons function
from the Combinatorica package (special thanks to those
who introduced me to this package) shows how quickly
the state space grows.
Needs["Combinatorica`"] // Quiet
max = 15;
For[n = 5, n <= max, n++,
Print["n = ",n, " " , AbsoluteTiming[c2b = 0.05 Compositions[20,
n] ;] ]
]
Therefore, the time it takes to generate all possible states
is prohibitive for large n (n > 10) and searches through
such a voluminous state space is not feasible.
A heuristic is being worked on that will, hopefully, reduce
the size of the state space while not sacrificing an optimum
solution for the objective function. Thank you again for all your
input into this.