Re: Simple n-tuple problem - with no simple solution
- To: mathgroup at smc.vnet.net
- Subject: [mg115863] Re: Simple n-tuple problem - with no simple solution
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Sun, 23 Jan 2011 05:35:48 -0500 (EST)
----- 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