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: [mg115869] Re: Simple n-tuple problem - with no simple solution
  • From: "Mr. Wizard" <gleam at flashmail.com>
  • Date: Sun, 23 Jan 2011 05:37:00 -0500 (EST)

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 




  • Prev by Date: Re: complex output for real integral
  • Next by Date: Re: complex output for real integral
  • Previous by thread: Re: Simple n-tuple problem - with no simple solution
  • Next by thread: Re: Simple n-tuple problem - with no simple solution