Partitions
- To: mathgroup at smc.vnet.net
- Subject: [mg32839] Partitions
- From: "Juan" <erfa11 at hotmail.com>
- Date: Fri, 15 Feb 2002 02:49:36 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
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