MathGroup Archive 2002

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

Search the Archive

Re: Partitions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg32882] Re: [mg32839] Partitions
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Mon, 18 Feb 2002 05:22:01 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

It seems to me your program is pretty fast and will be hard to beat. It 
is functional and has few obvious bottlenecks. The iterative approach 
below is actually slower in a single run but becomes faster if you 
repeat the computation a number of times as you can see  from the tests 
below (F2 is your F2):

F3[n_, k_, i_] /; (k*(i + 1) > n) := F3[n, k, i] = {};
F3[n_, 1, k_] /; k < n = {{n}};
F3[n_, k_, i_] :=
     F3[n, k, i] =
       Join @@ Table[Prepend[#, j] & /@ F3[n - j, k - 1, j], {j, i + 1, 
n}];
F3[n_, k_] := F3[n, k, 0]


In[6]:=
test=Table[{10*i,6},{i,6,12}]

Out[6]=
{{60,6},{70,6},{80,6},{90,6},{100,6},{110,6},{120,6}}

In[7]:=
Timing[Length[F2[##]]]&@@@test


Out[7]=
{{0.49 Second,3331},{1.17 Second,8442},{2.6 Second,18467},{5.16 Second,
     36308},{8.46 Second,65827},{14.8 Second,111999},{24.13 
Second,181038}}

In[8]:=
Timing[Length[F3[##]]]&@@@test

Out[8]=
{{1.66 Second,3331},{2.32 Second,8442},{4.01 Second,18467},{6.75 Second,
     36308},{10.11 Second,65827},{15.31 Second,111999},{22.56 
Second,181038}}




Of course for large values of n memory problems will arise. F3 will 
probably suffer from them sooner but if you really want to tackle huge 
problems you will probably have to write a backtracking version. It's 
likely to be slower for relatively small values but will be much more 
memory efficient. Similar problems have already been considered on this 
list.

Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
On Friday, February 15, 2002, at 04:49  PM, Juan wrote:

>
> Hello,
> Looking in the package DiscreteMath`Combinatorica`,I can not find a
> function to get the partitions of n, in  s parts.
>
> A way to get the partitions of n, in s parts with diferents numbers is 
> like
> that:
> << DiscreteMath`Combinatorica`
>
> In[1]:= F1[n_, s_] := Select[Partitions[n],
>    Length[#] == Length@Union[#] == s &]
>
> In[2]:= F1[60, 8]; // Timing
> Out[2]:= {170.315 Second, Null}
>
>
> (If you try F1[100,10] ... is useless)
>
>
> I need to do that for n=100, 200, 300,..., becouse I am writing a 
> package to
> play lottery.
>
> Using the brute force philosophy, I have wrote the function F2, which
> is hundred of times faster:
>
> In[3]:= F2[n_, s_, m_:1] :=
> Module[{a = Array[p, s - 1], y, v, q, t, b = Abs[s - 2]},
>     p[0] = m - 1;
>     y = FoldList[Plus, 0, Range[n - 1]];
>     v = {a, n - Plus @@ a} // Flatten;
>     q = n - FoldList[Plus, 0, a];
>     t = Table[{p[i + 1], p[i] + 1, (q[[i + 1]] - y[[s - i]])/(s - i)}, 
> {i,
> 0, s - 2}];
>     Flatten[Table[v, Evaluate[Sequence @@ t]], b]]
>
> In[4]:= F2[60, 8]; // Timing
> Out[4]:= {0.06 Second, Null}
>
> In[5]:= F1[20, 5]
> Out[5]:= {{10, 4, 3, 2, 1}, {9, 5, 3, 2, 1}, {8, 6, 3, 2, 1}, {8, 5, 4, 
> 2,
> 1}, {7, 6, 4, 2, 1}, {7, 5, 4, 3, 1}, {6, 5, 4, 3, 2}}
>
> In[6]:= F2[20, 5]
> Out[6]:= {{1, 2, 3, 4, 10}, {1, 2, 3, 5, 9}, {1, 2, 3, 6, 8}, {1, 2, 4, 
> 5,
> 8}, {1, 2, 4, 6, 7}, {1, 3, 4, 5, 7}, {2, 3, 4, 5, 6}}
>
> In[7]:= Length@F1[30, 5] == Length@F2[30, 5]
> Out[7]:= True
>
> In[8]:= F2[100, 10]; // Timing
> Out[8]:= {3.014 Second, Null}
>
> (F2 also works for m<=0)
>
> Surely F2 can be improbe or samebody knows something better.Please send 
> it
> here.
>
> If you want all the partitions of n in diferents numbers you have to 
> find
> F2[n, i] for i={1,2,3,...,(Sqrt[1+8n]-1)/2}
>
> Regards
> Juan
>
> _________________________________________________________________
> MSN Photos es la manera m·s sencilla de compartir e imprimir sus fotos:
> http://photos.latam.msn.com/Support/WorldWide.aspx
>
>
>
>



  • Prev by Date: Re: Mathematica, sounds and placing graphics
  • Next by Date: Iterators
  • Previous by thread: Partitions
  • Next by thread: partial fraction