what is the formula to select 4 numbers from a group of 48 numbers
(ex. 1 to 48) so that each set of 4 numbers will be unique for as many
times as possible.  Specifically, I am coordinating a dinner group
consisting of 48 couples.  Each dinner consists of 4 couples.  There
are 12 dinners each month. The challenge I have is to create a
multi-year list consisting of 4 couples so that each dinner will have
a unique combination of couples.  Your help is appreciated. If you are
aware of a program that does this, that would be helpful too.  I
suspect that this is a mathematical problem that is easily solved.

Hi, sondej-ga:

First, the easy answer.  [But stayed tuned; you may be asking a harder
problem!]

There are these many distinct combinations of 4 couples out of 48:

C(48,4) = 48!/(4!44!) = 194,580

If each dinner only had 4 couples, and there were 12 dinners per year,
then you could keep this up for a very long time indeed:

194,580 / 12 = 16,215 years

But I suspect what you mean is something more difficult.  

Perhaps you are thinking of having all 48 couples come to a dinner,
e.g. once a month.  Are you trying to arrange seating for the couples,
4 to a table, so that every couple appears 12 times a year?

I'm not sure how restrictive you might mean to be with the seatings. 
Is any seating okay, so long as no exact group of 4 couples is ever
perfectly repeated?  If so, there would still be enough combinations
to last hundreds of years.  1351 years and 3 months to be specific.

How about restricting things so that no two couples ever sit together
more than once?  This begins to reduce the problem to a "human"
dimension, since a couple cannot attend more than 15 dinners without
being seated with some other couple more than once.  [Each seating
will bring that couple in contact with three other couples, and so
after 15 dinners there would be only two couples left that they have
not been seated with.]

You are right in one sense, that these are mathematical problems. 
However depending on how restrictive you are in the seatings, they can
amount to hard problems in a difficult part of mathematics called
combinatorics.

I've written some software that can create these sorts of designs, and
if you can explain more precisely the seating restrictions I should be
able to compute one for you.  In combinatorics the designs of the most
restrictive type would be called "Steiner systems".

regards, mathtalk-ga

---

Request for Answer Clarification by sondej-ga on 09 Nov 2002 08:27 PST

Thanks for your quick response.  Here is a copy of your paragraph that
I think fits very nearly what I'm looking for...

"How about restricting things so that no two couples ever sit together
more than once?  This begins to reduce the problem to a "human"
dimension, since a couple cannot attend more than 15 dinners without
being seated with some other couple more than once.  [Each seating
will bring that couple in contact with three other couples, and so
after 15 dinners there would be only two couples left that they have
not been seated with.]".  

The dinners are periodic (monthly) with 4 couples at each dinner.
Another way to say this is that there would be 12 dinner groups per
month, each with 4 couples per dinner. The idea is to create an
opportunity for neighbors to meet each other. Therefore I would like a
way to create a list of couples (or numbers from 1 to 48) attending
the dinners so that there were no 2 couples going to the same dinner
until all combinations had been exhausted.  Example...couple
#1,#8,#12,#48 at one dinner location with couple #3,#9,#21,#32 going
to a different location etc. etc. It sounds like that after 15 months,
we would have repeats but that is ok. At least we would get a good
start on this project.  Perhaps the next 15+ months we could find a
way so that only 2 couples would have been together in previous
dinners.

---

Clarification of Answer by mathtalk-ga on 11 Nov 2002 22:54 PST

Hi, sondej-ga:

Unfortunately the scheduling is very dependent on the exact number of
couples/participants.  Let me describe a "couple" of other numbers
briefly, and then give the first 13 months of a schedule I have laid
out for the case of 48 couples.

If you had 12 couples, then you might hope that by sending them out in
three groups each month of 4 couples each, that every couple might
meet every other couple in (say) 4 months.  After all, any particular
couple could meet as many as three new couples at one dinner, so it
looks (from the perspective of just a single couple) as if four months
(and as many dinners) would suffice.  But one cannot arrange any
schedule after the first month in which repeated pairings of couples
are entirely avoided, at least six months would be needed for all
pairs to eat together, and with the restriction that no pair of
couples dines together more than twice the problem becomes impossible
altogether.

On the other hand if there were exactly 28 couples, the schedule can
be worked out "perfectly".  The couples dine together in groups of 4
each month for nine months, and each pair of couples dines together
exactly once!

So the case of 48 couples falls somewhere in the middle of these two
extremes.  It is not as frustrating as 12 couples, but not as neat as
28 couples either.

Here is a tentative schedule (I need to verify the correctness and see
how to extend it best to completion) for the first thirteen months. 
There are no repetitions (of pairings between couples) for the first
11 months.  Each dinner group in month 12 has one pair of couples who
have eaten together before, and each group in month 13 has two such
pairs.  But I think this is a good start because this delays the
"duplications" until fairly late in the schedule.

regards, mathtalk-ga

Month 1
[ 1, 2, 3, 4] [ 5, 6, 7, 8] [ 9,10,11,12] [13,14,15,16]
[17,18,19,20] [21,22,23,24] [25,26,27,28] [29,30,31,32]
[33,34,35,36] [37,38,39,40] [41,42,43,44] [45,46,47,48]

Month 2
[ 1,13,25,37] [ 2,14,26,38] [ 3,15,27,39] [ 4,16,28,40]
[ 5,17,29,41] [ 6,18,30,42] [ 7,19,31,43] [ 8,20,32,44]
[ 9,21,33,45] [10,22,34,46] [11,23,35,47] [12,24,36,48]

Month 3
[ 1,14,27,40] [ 2,15,28,41] [ 3,16,29,42] [ 4,17,30,43]
[ 5,18,31,44] [ 6,19,32,45] [ 7,20,33,46] [ 8,21,34,47]
[ 9,22,35,48] [10,23,36,37] [11,24,25,38] [12,13,26,39]

Month 4
[ 1,15,26,44] [ 2,16,27,45] [ 3,17,28,46] [ 4,18,29,47]
[ 5,19,30,48] [ 6,20,31,37] [ 7,21,32,38] [ 8,22,33,39]
[ 9,23,34,40] [10,24,35,41] [11,13,36,42] [12,14,25,43]

Month 5
[ 1,16,36,43] [ 2,17,25,44] [ 3,18,26,45] [ 4,19,27,46]
[ 5,20,28,47] [ 6,21,29,48] [ 7,22,30,37] [ 8,23,31,38]
[ 9,24,32,39] [10,13,33,40] [11,14,34,41] [12,15,35,42]

Month 6
[ 1,17,33,48] [ 2,18,34,37] [ 3,19,35,38] [ 4,20,36,39]
[ 5,21,25,40] [ 6,22,26,41] [ 7,23,27,42] [ 8,24,28,43]
[ 9,13,29,44] [10,14,30,45] [11,15,31,46] [12,16,32,47]

Month 7
[ 1,18,35,46] [ 2,19,36,47] [ 3,20,25,48] [ 4,21,26,37]
[ 5,22,27,38] [ 6,23,28,39] [ 7,24,29,40] [ 8,13,30,41]
[ 9,14,31,42] [10,15,32,43] [11,16,33,44] [12,17,34,45]

Month 8
[ 1,19,34,39] [ 2,20,35,40] [ 3,21,36,41] [ 4,22,25,42]
[ 5,23,26,43] [ 6,24,27,44] [ 7,13,28,45] [ 8,14,29,46]
[ 9,15,30,47] [10,16,31,48] [11,17,32,37] [12,18,33,38]

Month 9
[ 1,20,30,38] [ 2,21,31,39] [ 3,22,32,40] [ 4,23,33,41]
[ 5,24,34,42] [ 6,13,35,43] [ 7,14,36,44] [ 8,15,25,45]
[ 9,16,26,46] [10,17,27,47] [11,18,28,48] [12,19,29,37]

Month 10
[ 1,21,28,42] [ 2,22,29,43] [ 3,23,30,44] [ 4,24,31,45]
[ 5,13,32,46] [ 6,14,33,47] [ 7,15,34,48] [ 8,16,35,37]
[ 9,17,36,38] [10,18,25,39] [11,19,26,40] [12,20,27,41]

Month 11
[ 1,23,29,45] [ 2,24,30,46] [ 3,13,31,47] [ 4,14,32,48]
[ 5,15,33,37] [ 6,16,34,38] [ 7,17,35,39] [ 8,18,36,40]
[ 9,19,25,41] [10,20,26,42] [11,21,27,43] [12,22,28,44]

Month 12
[ 1,22,31,41] [ 2,23,32,42] [ 3,24,33,43] [ 4,13,34,44]
[ 5,14,35,45] [ 6,15,36,46] [ 7,16,25,47] [ 8,17,26,48]
[ 9,18,27,37] [10,19,28,38] [11,20,29,39] [12.21,30,40]

Month 13
[ 1,24,32,47] [ 2,13,33,48] [ 3,14,34,37] [ 4,15,35,38]
[ 5,16,36,39] [ 6,17,25,40] [ 7,18,26,41] [ 8,19,27,42]
[ 9,20,28,43] [10,21,29,44] [11,22,30,45] [12,23,31,46]

---

Request for Answer Clarification by sondej-ga on 12 Nov 2002 06:07 PST

Wow!  When I first was given this problem (my wife), I had assumed
that it was a fairly simple formula.  Now I'm beginning to think that
it is much more complicated.  I wonder if there is a piece of code
that allows you to input the number of couples so that you get a
schedule as you so nicely provided.  There are 1000s of dinner groups
around the country.  I would assume that they are all challenged with
the same problem.  On the other hand, they may not care.  I guess the
other approach is to just put the numbers in a random number generator
and if duplicates happen, so be it.  Thanks again for your help on
this.  If you come up with more info, it too will be appreciated.

---

Clarification of Answer by mathtalk-ga on 12 Nov 2002 07:27 PST

Yes, it is fascinating just how difficult such simply stated problems
can be.

The scheduling of "foursomes" is typically associated in the sports
world with golf tournaments.  While there is considerable inexpensive
software "out there" for scheduling matches involving two participants
(or teams), the problem of scheduling with four participants is not
handled by most of these packages.

Here is a discussion of an application of one combinatorial search
program to a "golf" schedule involving 32 players (or couples, in your
application):

http://www.mozart-oz.org/documentation/fst/node6.html

My own software is written in Prolog, a language especially suited to
combinatorial searches.  However some "insight" is needed to make an
effective search.  As discussed in the beginning of this thread, there
are nearly 200,000 possible seatings of four couples out of 48.  Even
a very powerful computer could not check all possible selections of
these seatings to form the minimal monthly schedules by brute force
(though such an approach is possible with say 12 couples).

In my case the "insight" was provided by a mathematical technique
known as the method of difference sets.  After setting the first
month's seating in an "obvious" way (one can simply number the couples
to correspond to this seating), I explored the possibility of dividing
the 48 couples into four classes of 12 couples:

couples 1 through 12
couples 13 through 24
couples 25 through 36
couples 37 through 48

and producing from that 12 months of dinners in which each couple
would dine exactly once with each of the 36 couples in the three
classes to which they themselves do not belong.  That would go a long
way toward completing the solution of the specific problem of 48
couples, as it would remain (after the first month plus 12 more
months) only to set certain "intra-group" seatings within each class
of 12 (which as I mentioned is an awkward but understood number of
participants to work with).  I did not succeed in finding a "perfect"
twelve month schedule of the type I wanted, though I did find the one
outlined in which only two months have repetitions (and these of
limited numbers).

The computation was so intensive that it ran my laptop down, even
while plugged into the wall, over a period of about an hour!  I plan
to give it another shot with a fast desktop system I'm building for my
parents. . .

I will be able to post additional comments (as you will, too) until
your question expires next month (Dec. 8).  Let me know if I can be of
assistance with your very interesting problem.

best wishes, mathtalk-ga

The question is a bit like arranging golf outings, with four players
grouped for a particular tee time.  The question is then like asking
how many weeks can be played without repeating a foursome (versus how
many weeks can be played without having any two players in the same
foursome more than once).

-- mathtalk-ga

Hi, sondej:

Thanks for the clarification.  I am working on several approaches to
see which might give the most elegant schedule.

regards, mathtalk

Great.  Ideally, the technique would not be limited to 48.  I honestly
don't know the exact number but am guessing that it is around 50 +/-
10. Thanks for your help on this.