MathGroup Archive 2000

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

Search the Archive

Re: Help on Partitions, Again!!!

  • To: mathgroup at smc.vnet.net
  • Subject: [mg24661] Re: Help on Partitions, Again!!!
  • From: d8442803 at student.nsysu.edu.tw (Wen-Feng Hsiao)
  • Date: Mon, 31 Jul 2000 09:23:28 -0400 (EDT)
  • Organization: NSYSU
  • References: <8lt1mt$2m2@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

> In[ ] = f [ {A,B,C,D,E,F},{3,3}]
> Out [ ] = { { {A,B,C},{D,E,F} }, { {
> A,B,F},{C,D,E}},...................} and so on.
> In [ ] = Length[%]
> Out [ ] = 10
Dear DeMelo,

You can still make use of KSubsets to obtain what you want.
A basic idea is: Suppose we want to partition a list into combinations 
with element numbers n1 and n2. Then we can use KSubsets to find the 
"combinations" of n1-element and n2-element, separately; followed by 
concating them, and checking if they fulfill the requirements: no 
duplication. Specifically,

set1 = KSubsets[lst, n1];
set2 = KSubsets[lst, n2];
result = Select[Outer[List, n1, n2, 1], 
Union[Sequence@@#]==Length[lst]&];
result = Union[Sort /@ result];  (* remove duplicated lists *)

The final function could be:

<< DiscreteMath`Combinatorica`
comb[lst_List, parts_List] := 
  Module[{len = Length[lst], partlen = Length[parts], sets, matches},
    If[Plus @@ parts  != len, Print["Partitions are not correct."]; 
      Return[]];
    sets = KSubsets[lst, #] & /@ parts;
    matches = 
      Select[Flatten[Outer[List, Sequence @@ sets, 1], partlen - 1], 
        Length[Union[Sequence @@ #]] == len &];
    matches = Union[Sort[#] & /@ matches];
    Return[matches];]

In[7]:=
comb[{a, b, c, d}, {2, 1, 1}]
Out[7]=
{{{a}, {b}, {c, d}}, {{a}, {c}, {b, d}}, {{a}, {d}, {b, c}}, 
 {{b}, {c}, {a, d}}, {{b}, {d}, {a, c}}, {{c}, {d}, {a, b}}}

In[8]:=
comb[{a, b, c, d, e, f}, {3, 3}]
Out[8]=
{{{a, b, c}, {d, e, f}}, {{a, b, d}, {c, e, f}}, {{a, b, e}, {c, d, f}},  
 {{a, b, f}, {c, d, e}}, {{a, c, d}, {b, e, f}}, {{a, c, e}, {b, d, f}},  
 {{a, c, f}, {b, d, e}}, {{a, d, e}, {b, c, f}}, {{a, d, f}, {b, c, e}},   
 {{a, e, f}, {b, c, d}}}

Regards,

Wen-Feng


  • Prev by Date: Re: getting module output in replace form
  • Next by Date: Re: Commuting Matrices
  • Previous by thread: Re: Help on Partitions, Again!!!
  • Next by thread: Re: Help on Partitions, Again!!!