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