MathGroup Archive 1997

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

Search the Archive

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


  • Prev by Date: ParametricPlot Remark
  • Next by Date: Re: Confused about replacement rules
  • Previous by thread: ordered pairs
  • Next by thread: Ordered Pairs