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: [mg115845] Re: Simple n-tuple problem - with no simple solution
  • From: DrMajorBob <btreat1 at austin.rr.com>
  • Date: Sat, 22 Jan 2011 03:23:57 -0500 (EST)

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

On Fri, 21 Jan 2011 03:35:46 -0600, Bob Hanlon <hanlonr at cox.net> wrote:

>
> Load Combinatorica then use  0.05 * Compositions[20, n]
>
> Needs["Combinatorica`"] // Quiet
>
> n = 5;
>
> Timing[c1 = Select[Tuples[Table[Range[0, 1.0, .05], {n}]], Total[#] == 1  
> &];]
>
> {14.4972, Null}
>
> Timing[c2 = 0.05 Compositions[20, n];]
>
> {0.044528, Null}
>
> c1 == c2
>
> True
>
>
> Bob Hanlon
>
> ---- Don <donabc at comcast.net> wrote:
>
> =============
> Problem: Given an n-tuple  (n >= 1). with each element  able to take
> on the values in
> Range[0, 1.0, .05] , produce all the n-tuples that sum to 1.0.
>
> The most direct way to solve this problem is to generaate all possible
> n-tuples and Select out all those that sum to 1.0.
>
> For example, when n = 2 :
>
> n = 2;
> Select[Tuples[Table[Range[0, 1.0, .05], {n}]], Total[#] == 1 &]
>
> The problem with this solution is that the number of n-tuples that are
> generated before the Select is used grows exponentially fast as a
> function
> of n - causing the system to run out of memory (RAM) very quickly.
>
> Is there a more memory efficient way to solve this problem that
> doesn't
> use so much memory but still is not too slow in terms of processor
> time?
>
> Thank you.
>
>
>


-- 
DrMajorBob at yahoo.com


  • Prev by Date: Re: Problems Exporting to PDF
  • Next by Date: a bug in Mathematica 7.0?
  • Previous by thread: Re: Simple n-tuple problem - with no simple solution
  • Next by thread: Re: Simple n-tuple problem - with no simple solution