Getting hierarchies of partitions

• To: mathgroup at smc.vnet.net
• Subject: [mg36472] Getting hierarchies of partitions
• From: Emilio Martin-Serrano <EMartinSerrano at houston.sns.slb.com>
• Date: Sun, 8 Sep 2002 03:30:52 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```Group,

Can anyone help me with the following? I guess this is something trivial
for most of you, but I have being struggling with it for  weeks.

The problem is to construct a taxonomic hierarchy whose structure is hereby
described by example:

<< DiscreteMath`Combinatorica`

n[1]:=  m = 10;

(*with the following I get the 1th level (1--element) partition*)

in[2]:= ks1 = Partition[Range[m], 1]

(*Now the following gives all the 2th-level (?) different partitions that
can be set up by joining two elements in the 1-element partition and
leaving the rest as they are?*)

(*First, these are all possible  'joinings'  to generate the two elements
'pieces' from 1th level (1--element) partition*)

in[3]:= ks2 = KSubsets[Range[m], 2]

(*And this generates all the 2th-level (?) different partitions that can be
set up by joining two elements in the 1-element partition and leaving the
rest as they are.*)

in[4]:= p2 = MapThread[Complement[Append[#1, #2], (Sequence @@ {#} & /@
Partition[#2, 1])] &, {Array[ks1&, Length[ks2]], ks2}];
Length[p2]

in[5]:= p2[[1]]
out[5]:= {{3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {1, 2}}
in[6]:= p2[[Length[p2]]]
out[6]:= {{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9, 10}}

(*compute in[4] t and see the full output*)

(*Now I need to solve the problem of given the ith-level (?) different
partitions to set up all the i+1th different partitions by joining two
elements in the ith level partition and leaving the rest  as they are? *)

(*for example given  the following  2th-level partition*)

{3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {1, 2}

(*we should get*)

{{{4}, {5}, {6}, {7}, {8}, {9}, {10}, {1, 2, 3}},
{{3}, {5}, {6}, {7}, {8}, {9}, {10}, {1, 2, 4}},
{{3}, {4}, {6}, {7}, {8}, {9}, {10}, {1, 2, 5}},
{{3}, {4}, {5}, {7}, {8}, {9}, {10}, {1, 2, 6}},
{{3}, {4}, {5}, {6}, {8}, {9}, {10}, {1, 2, 7}},
{{3}, {4}, {5}, {6}, {7}, {9}, {10}, {1, 2, 8}},
{{3}, {4}, {5}, {6}, {7}, {8}, {10}, {1, 2, 9}},
{{3}, {4}, {5}, {6}, {7}, {8}, {9}, {1, 2, 10}}}

(*The process would end up to *)

{1,{2,3,4,5,6,7,8,9,10}}
{2,{1,3,4,5,6,7,8,9,10}}
{3,{1,2,4,5,6,7,8,9,10}}
{4,{1,2,3,5,6,7,8,9,10}}
{5,{1,2,3,4,6,7,8,9,10}}
{6,{1,2,3,4,5,7,8,9,10}}
{7,{1,2,3,4,5,6,8,9,10}}
{8,{1,2,3,4,5,6,7,9,10}}
{9,{1,2,3,4,5,6,7,8,10}}
{10,{1,2,3,4,5,6,7,8,9}}

(* and*)

{1,2,3,4,5,6,7,8,9,10}

Thanks

Emilio Martin-Serrano

```