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]:=

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.

```

• Prev by Date: Re: Possible Bug in ArcTan ?
• Next by Date: Re: Listing the partitions of a set
• Previous by thread: Re: Listing the partitions of a set
• Next by thread: Re: Listing the partitions of a set