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

*To*: mathgroup at smc.vnet.net*Subject*: [mg115845] Re: Simple n-tuple problem - with no simple solution*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Sat, 22 Jan 2011 03:23:57 -0500 (EST)

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 On Fri, 21 Jan 2011 03:35:46 -0600, Bob Hanlon <hanlonr at cox.net> wrote: > > Load Combinatorica then use 0.05 * Compositions[20, n] > > Needs["Combinatorica`"] // Quiet > > n = 5; > > Timing[c1 = Select[Tuples[Table[Range[0, 1.0, .05], {n}]], Total[#] == 1 > &];] > > {14.4972, Null} > > Timing[c2 = 0.05 Compositions[20, n];] > > {0.044528, Null} > > c1 == c2 > > True > > > Bob Hanlon > > ---- Don <donabc at comcast.net> 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. > > > -- DrMajorBob at yahoo.com