Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

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

Search the Archive

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.


  • 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