Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Grouping problem

3 views
Skip to first unread message

MM

unread,
Feb 4, 2002, 4:25:00 PM2/4/02
to
Hi,

I'm desperatly trying to figure out a (fairly) effective algorithm for
finding all possible "groupings" of a given number of individuals (or
numbers or whatever). Suppose I have k*m individuals that I want to divide
into k different groups with m individuals in each group. Also let a group
for example [1,2,3] be "the same as"/equivalent to the groups [1,3,2],
[2,1,3], [2,3,1], [3,1,2], and [3,2,1]. Then it is easy to show (if I did it
correctly) that the number G of possible groupings is:

(k*m)!
G = ------------
k
k! * (m!)

i.e. (k*m)! / (k!*(m!)^k) if the above is not represented properly.

For example k = 2, m = 2 gives G = 3, the following groupings:
1) [1,2]+[3,4]
2) [1,3]+[2,4]
3) [1,4]+[2,3]

So, if this could be understood, then maybe someone can help me with some
kind of algorithm for create all G groupings given k and m. I intend to use
MATLAB, and probably use a matrix for representing the groupings. In the
above example a matrix

[ 1 2 3 4 ]
[ 1 3 2 4 ]
[ 1 4 2 3 ]

(or equivalent) is desired.

I really hope someone has some ideas.

Thanks in advance,

UL

0 new messages