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

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

No... I did not solve a different problem. My solutions can easily be converted to the other form, just as they can be converted to mine. I tested to see that all the methods return the same number of solutions (after removing rearrangements), and I tested to see that all of them (including mine) solve the problem. I had suggested IntegerPartitions and FrobeniusSolve, earlier, and I don't doubt that IntegerPartitions is faster than Solve, but I'd forgotten to look at those. Bobby On Sat, 22 Jan 2011 18:47:09 -0600, Daniel Lichtblau <danl at wolfram.com> wrote: > > > ----- Original Message ----- >> From: "DrMajorBob" <btreat1 at austin.rr.com> >> To: mathgroup at smc.vnet.net >> Sent: Saturday, January 22, 2011 2:23:57 AM >> Subject: [mg115845] Re: Simple n-tuple problem - with no simple solution >> 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 = 5; addends = Rationalize@Range[0, 1.0, 0.05]; >> >> Clear[t1] >> t1[range_List, n_Integer] := >> Module[{addends = Rationalize@range, multipliers, m, sum, >> nonNegative}, >> multipliers = Array[m, Length@range]; >> sum = Total@multipliers; >> nonNegative = And @@ Thread[multipliers >= 0]; >> Sort[multipliers /. >> Solve[{multipliers.addends == 1, nonNegative, sum == n}, multipliers, >> Integers]]] >> >> Length@t1[addends, n] // Timing >> >> {1.44372, 192} >> >> "Sseziwa Mukasa" < mukasa at jeol.com > >> >> {First@Timing[ >> sm = Flatten[ >> Outer[If[Plus[##] == 1, {##}, Sequence @@ {}] &, >> Sequence @@ Table[addends, {n}]], n - 1];], Length@Union[Sort /@ >> sm]} >> >> {23.6318, 192} >> >> Daniel Lichtblau: >> >> getSolutions[sum_, max_, 1] := If[max < sum, {}, {{sum}}] >> getSolutions[sum_, max_, n_] := >> Module[{subsols}, Union[Flatten[Table[subsols = getSolutions[j, max, n >> - >> 1]; >> If[Length[subsols] >= 1, >> Table[Insert[subsols[[i]], sum - j, k], {k, 1, n}, {i, >> Length[subsols]}], {}], {j, Max[sum - max, 0], sum}], 2]]] >> >> {First@Timing[dl = getSolutions[20, 20, n];], dl = Union[Sort /@ dl]; >> Length@Union[Sort /@ dl], Total /@ dl // Union} >> >> {0.538832, 192, {20}} >> >> Bob Hanlon: >> >> Needs["Combinatorica`"] // Quiet >> >> {First@Timing[bh = Compositions[20, n]/20;], Length@Union[Sort /@ bh], >> Total /@ bh // Union} >> >> {0.167242, 192, {1}} >> >> Bob looks very good, and Sseziwa seems out of the running. >> >> Next for n = 7: >> >> n = 7; >> Length@t1[addends, n] // Timing >> >> {1.85135, 364} >> >> {First@Timing[dl = getSolutions[20, 20, n];], dl = Union[Sort /@ dl]; >> Length@Union[Sort /@ dl]} >> >> {21.6415, 364} >> >> {First@Timing[bh = Compositions[20, n]/20;], Length@Union[Sort /@ bh]} >> >> {1.79257, 364} >> >> Daniel seems out of the running. >> >> For n = 9: >> >> n = 9; >> Length@t1[addends, n] // Timing >> >> {2.04216, 488} >> >> {First@Timing[bh = Compositions[20, n]/20;], Length@Union[Sort /@ bh]} >> >> {29.1514, 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. >> >> Bobby >> [...] > > You are comparing melons to melanomas. The other codes solve a different > problem, one that has many more solutions than the one you did. For > example, at n=10 it has more than 10^7 solutions. Takes considerable > time and memory to spawn them, even using better code than what is shown > above. > > Solve does indeed use ILP behind the scenes, and it works well enough. > But the builtin Integerpartitions will do this faster. Using the > notation I had previously (not that it was particularly good, but being > consistent here). > > getSolutions2[sum_, max_, n_] := > IntegerPartitions[sum, {n}, Range[0, max]] > > In[306]:= Timing[Length[getSolutions2[20, 20, 25]]] > Out[306]= {0., 627} > > Daniel Lichtblau > Wolfram Research -- DrMajorBob at yahoo.com