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
>
>
>
>