MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Simple n-tuple problem - with no simple solution
  • Next by Date: Re: problem with LessEqual::nord:
  • Previous by thread: Re: Simple n-tuple problem - with no simple solution
  • Next by thread: Re: Simple n-tuple problem - with no simple solution