Re: Simple n-tuple problem - with no simple solution
- To: mathgroup at smc.vnet.net
- Subject: [mg115876] Re: Simple n-tuple problem - with no simple solution
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Sun, 23 Jan 2011 17:32:25 -0500 (EST)
"Range[...] can be replaced with a different list, as in your method."
IntegerPartitions works if the range is in the form Range[0, 1, 1/k] for
positive integer k... or a subset of such.
Solve is slower, but it should work for any set of reals, positive or
negative, provided only that (a) Rationalize doesn't yield prohibitively
large denominators, (b) solutions exist after rationalization, and (c) a
rationalized version of the problem is sufficient for the purpose. Those
conditions are difficult to satisfy for random reals, admittedly.
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