Re: ordered pairs
- To: mathgroup at smc.vnet.net
- Subject: [mg7195] Re: ordered pairs
- From: wself at viking.emcmt.edu (Will Self)
- Date: Wed, 14 May 1997 01:11:32 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Wouter L. J. Meeussen asked the following:
-----------------------------------------------------------------------
Partitions[6,2]
{{2,2,2},{2,2,1,1},{2,1,1,1,1},{1,1,1,1,1,1}}
for the first partition {2,2,2}, I would like all possible combinations:
12 34 56
12 35 46
12 36 45
13 24 56
13 25 46
13 26 45
14 23 56
14 25 36
14 26 35
15 23 46
15 24 36
15 26 34
16 23 45
16 24 35
16 25 34
where each pair is ordered, and the pairs themselves are ordered according
to the first element.
and analogously for the other partitions.
If there is no pre-defined (combination of) function(s), any hints as to the
way how to tackle this procedurally?
wouter.
----------------------------------------------------------------
I don't know about trying to do it procedurally, but the following
recursive definition works. I call the function MeeussenPartitions.
Examples:
MeeussenPartitions[{10,20,30,40,50,60}, {2,1,3}]
MeeussenPartitions[{10,20,30,40,50,60}, {2,2,2}]
The first argument here is the ensemble, the second is the partition list.
Note that the partition list does not have to be decreasing.
The definition comes in three parts.
First, if the partition list consists of just one element, then you just want
the k-subsets of the original ensemble. However, you want to enclose each one
in a list, because you are creating a list of lists of subsets. Note that
you need KSubsets from the Combinatorica package.
MeeussenPartitions[ensemble_,{k_}]:= List/@ KSubsets[ensemble,k]
Second, if the partition list has more than one entry and the first element of
the partition list is 1, then for each j you remove the jth element from
the ensemble and create listj = MeeussenPartitions of the resulting ensemble
and the partition list that you get by ignoring the 1. Then you prepend the
jth element (put into its own list) at the first of each of the sets in
listj. Then put these listj's all together in one big list using Table
and Flatten.
MeeussenPartitions[ensemble_,{1, sequ__}]:=
Flatten[Table[
Prepend[#,{ensemble[[j]]}]& /@ MeeussenPartitions[Drop[ensemble,{j}],{sequ}],
{j,1,Length[ensemble],1}],1]
Third, if the partition list has more than one entry and the first element of
the partition list is greater than 1, then you remove the first element of the
ensemble to get a smaller ensemble, and you subtract 1 from the first entry
to get a smaller partition list. You create MeeussenPartitions using these
resulting arguments, and then modify it by going through the resulting list of
partitions of the smaller ensemble, and sticking the first element of the
original ensemble back into the first set appearing in each entry in the list.
MeeussenPartitions[ensemble_,{k_, sequ__}]:=
(ReplacePart[#, Prepend[#[[1]], ensemble[[1]]], 1])& /@ MeeussenPartitions[Drop[ensemble,1],{k-1,sequ}]
Will Self
Montana