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