Any mathematical insight???

[Zyrenthian]

Hi All,
I play in a card league every tuesday night and at the beginning of the season, the bartender who runs the league asked me if it was possible to create a unique schedule every week so every player was partnered with every other player. The question came about because a few of the players complain that they sit with the same people almost every week. What I have been trying to do for the past 18 weeks is to come up with a new way to generate the schedule with the following restrictions...

1. Each player will be paired up with a new partner every week.
2. Each player will not sit with someone who was at their table the privious week
3. A table constists of 4 players (2 vs 2) where Player A has an opponent on either side and his partner sitting across from him
4. The tournament will last no more then 20 weeks and in the case of 16 or 20 players, players WILL be partnered with someone they partnered with prior. (pigeon hole principle)


The card game is pitch (high/low/jack or set back)
The number of players in the league is a multiple of 4 and will only be 16,20,or 24. Max and min was set by the bartender.

I am not asking for code, I am asking for any ideas on how to go about generating a unique schedule for every week. I have tried arrays, linked lists, circular linked lists, and many other ideas but all produce either one of 2 results...

a unique sequence for part of the season but not the whole season

a sequence that repeats itself after x sequences are generated.

Any insight to this would be greatly appreciated.

matt

 

[fheyn]

Hi, very interesting.
I myself spent a lot of studying and creating schedules.
I think what you should do is :
a) for creating the partners use a schedule which contains
all the players.
b) for the opponents use a second schedule which contains
the pairings of the first one.

example : there are 8 players.

first step create 4 pairings. 1/2, 3/4, 5/6, 7/8.
second step : now you have 4 elements which will give
combinations like :

1/2 - 3/4, 5/6 - 7/8
1/2 - 5/6, 3/4 - 7/8
1/2 - 7/8, 3/4 - 5/6

Hope this helps

 

[Jeffray]

I used to work on the constraint satisfaction problem.
Basically CSP deals with a set of finite domain(mostly integer) variables, there are a few constraints on the variables. Solveing a CSP is to find values for every variable so that every constraint will be met.

The problem here is a scheduling one, which is one instance of CSP. A lot of efforts have been put on the general solving methods of CSP problems. The key techniques used are constraint propagation, domain reduction and search. Search the keywords constraint programming or constraint satisfaction on the internet, you can get a lot of information and get ideas from that.

 

[ross12]

If I am not wrong your problem is a combinatorial problem. There is a large number of solutions and as the weeks go by some solutions become taboo, in other words cannot be used again.

I have used AI methods to solve hard problems in the arena of 2D nesting and can see some similarities. Basically, you could use a technique called taboo searching. Other methods such as Genetic algorithms could also be used to find solutions. Some of these obviously will not be allowed as they have already been used. In your program you need a database of used solutions.

I use the terms solution, problem and search space which are very general as your problem is one of many examples of combinatorial problems.

I hope this has helped you....

 

[Zyrenthian]

Yes it is... i have broken out my combinatorics book and calculated how many combinations of 4 exist, how many combinations of 2, i have done the permutations and all the other stuff. I actually calculated how many possible ways there were to have a valid solution. I was actually thinking of using graph theory as my next step, possibly with a uni-directional graph but that too proves to be mind boggleing.

I will be searching the web on all the ideas posted here and I do hope to find a solution. If/When I do find a solution, I will be more then happy to share my code with anyone.

Until that solution comes, please keep the ideas rolling... You can never have TOO much information

Thanx for all your help so far
Matt

 

[fheyn]

well, there's a lot of theory.
practically setting up a schedule should be like this:

once again you have 8 players.

in the first step it gives you the pairings :
1 / 2
3 / 4
5 / 6
7 / 8

now you rotate one side until your initial pairings
come up again.
In all that will give you four sets of pairings.

Now what you lack are the pairings of elements on one
side (which will be three more sets)

Solution to this is : while rotating the elements (as in
step one) you have to shift one element from one side to
the other and after all the rotating and shifting is done
you'll get the seven sets of pairings.

This looks rather unmathematical, but with the theory of
combinations you get the problem that 1/2 not is 2/1 which
you don't need for solving your problem.

just give your e-mail adress and you can get the formula
for setting up a schedule as described above (and it's for
n elements not for 8).

hope this helps

 

[Zyrenthian]

Sure... any help is always appreciated

zyrenthian@cox.net

Matt

 

[Zyrenthian]

One thing I forgot to mention was that week one is fixed as

GIVEN:
n = # of players
n%4 = zero
16<=n<=24


WEEK 1:
x[sub]1[/sub]&x[sub]2[/sub] VS x[sub]3[/sub]&x[sub]4[/sub] ... x[sub]n-3[/sub]&x[sub]n-2[/sub] VS x[sub]n-1[/sub]&x[sub]n[/sub]

with that in mind... we know how many different table combinations exist for the remaining weeks with this formula

(n CHOOSE 4) - ((n-2) CHOOSE 2) or in code
==========================================================================================

	// we will ignore any combinations of the original week 1 setup
	// ie 1&2 vs 3&4 etc..

	// val CHOOSE 4

	int numerator = val*(val-1)*(val-2)*(val-3); // max =24*23*22*21
	int denominator = 4*3*2;

	int totalTables =  numerator/denominator;

	// (val-2) CHOOSE 2 for week one... subtract this
	numerator = val*(val-1);
	denominator = 2;

	return totalTables - (numerator/denominator);

==========================================================================================

Well, that is about as far as I am. It will be a very memory intesive program and since I have been working on it in my spare time, posts will always be welcome until I post that I figured it out.

Thanx,
Matt

 

[Zyrenthian]

My math is a bit off... i will repost the formula when I re-write it... it is an overshot which I just noticed with some debug code.

Matt

 

[woolstar]

This reminds me of a programming problem at a computer programming contest I was once in. The problem was to create &quot;magic squares&quot;. I worked on solving this problem in a combinatorial way and didn't finish in the time allowed. The published solution just generated every square possible, and checked to see if it was valid before printing it out.

If the number of players is small, I would just write a small program to generate every possibility, and prune the unwanted ones. Brute force has its place.