Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

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: [mg115875] Re: Simple n-tuple problem - with no simple solution
  • From: DrMajorBob <btreat1 at austin.rr.com>
  • Date: Sun, 23 Jan 2011 17:32:14 -0500 (EST)

If we insist on a solution REPRESENTATION that blows up memory for modest  
n, there's no use looking for a solution ALGORITHM that does not. No such  
algorithm can exist.

That is, it makes no sense to return 10 million solutions, when 600 -- in  
a more compact form -- yield the same information.

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: Mathematica 20x slower than Java at arithmetic/special functions, is
  • Next by Date: Re: Simple n-tuple problem - with no simple solution
  • Previous by thread: Re: Simple n-tuple problem - with no simple solution
  • Next by thread: Re: Simple n-tuple problem - with no simple solution