Re: Listing the partitions of a set
- To: mathgroup at smc.vnet.net
- Subject: [mg65307] Re: Listing the partitions of a set
- From: "Valeri Astanoff" <astanoff at yahoo.fr>
- Date: Sat, 25 Mar 2006 05:17:43 -0500 (EST)
- References: <e0022d$plp$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
A colleague of mine suggested this recursive cache solution
that outperforms my own poor solution :
In[1]:=
myPartitions[1] = {{{1}}};
myPartitions[n_Integer /; n>1]:=myPartitions[n]=
Module[{grow},
grow[li_List,m_]:=
Table[ReplacePart[li,Append[li[[k]],m],k],{k,1,Length[li]}];
Sort[
Sort/@Join[Flatten[grow[#,n]& /@ myPartitions[n-1],1],
Append[#,{n}]& /@myPartitions[n-1]] ]
];
myPartitions[li_List/;VectorQ[li]&&Length[li]>0]:=
myPartitions[Length[li]]/.Thread[Range[Length[li]]\[Rule]li];
In[4]:=myPartitions[{a,b,c,d}]
Out[4]=
{{{a,b,c,d}},{{a},{b,c,d}},{{b},{a,c,d}},
{{c},{a,b,d}},{{d},{a,b,c}},{{a,b},{c,d}},
{{a,c},{b,d}},{{a,d},{b,c}},{{a},{b},{c,d}},
{{a},{c},{b,d}},{{a},{d},{b,c}},{{b},{c},{a,d}},
{{b},{d},{a,c}},{{c},{d},{a,b}},{{a},{b},{c},{d}}}
In[5]:=Length[%]
Out[5]=15
In[6]:=mp=myPartitions[{a,b,c,d,e,f,g,h}]//Timing;
In[7]:=mp//First
Out[7]=0.141 Second
In[8]:=mp//Last//Length
Out[8]=4140
In[9]:=mp//Last//Short
Out[9]//Short=
{{{a,b,c,d,e,f,g,h}},<<4138>>,{{a},{b},{c},{d},{e},{f},{g},{h}}}
v.a.