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

*To*: mathgroup at smc.vnet.net*Subject*: [mg115875] Re: Simple n-tuple problem - with no simple solution*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Sun, 23 Jan 2011 17:32:14 -0500 (EST)

If we insist on a solution REPRESENTATION that blows up memory for modest n, there's no use looking for a solution ALGORITHM that does not. No such algorithm can exist. That is, it makes no sense to return 10 million solutions, when 600 -- in a more compact form -- yield the same information. Bobby On Sun, 23 Jan 2011 04:37:00 -0600, Mr. Wizard <gleam at flashmail.com> wrote: > DrMajorBob wrote: >> I didn't think rearrangements of a solution mattered, so my approach was >> different... and I found that Solve is pretty darn fast! >> >> My approach also allows Range[0,1,.05] to be replaced with almost any >> list >> of reals, though I didn't experiment with that. >> >> Here are some timings. >> >> 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. > > > Before replies started appearing on the list, I sent a private > message to Don with my recommendation. Leonid Shifrin gave a similar > solution, and you also suggested a look at IntegerPartitions. In my > testing it is far and away faster. Compared to the original method: > > f1 = Select[Tuples[Table[Range[0, 1.0, .05], {#}]], Total[#] == 1 &] &; > f2 = Union @@ Permutations /@ # &@N@IntegerPartitions[1, {#}, > Range[0, 1, 1/20]] &; > Timing[ r1 = f1[5]; ] > Timing[ r2 = f2[5]; ] > r1 === r2 > > Out[1]= {8.734, Null} > Out[2]= {0.016, Null} > Out[3]= True > > If the permutations are not required: > > f3 = N@IntegerPartitions[1, {#}, Range[0, 1, 1/#2]] &; > Timing[Length@f3[25, 20]] > Timing[Length@f3[17, 50]] > > Out[4]= {0., 627} > Out[5]= {0.704, 161144} > > Range[...] can be replaced with a different list, as in your method. > > Paul > > > -- DrMajorBob at yahoo.com