How would you do this?

Here is the situation:
I have been asked to run a dart tournament. 16 players have entered.

The tournament will be run on five different nights. The venue has 4 dartboards.

I would like to split the 16 players into 4 groups of 4 each. Over the 5 nights, each player must play each other player once. Players may not play the same player twice.

The players in each group will change for each night.

Any idea of how to schedule this?

I can get to the third night working it out on paper, but for nights 4 & 5 I can't avoid conflicts.

This is off the cuff, but by doing different permutations of the square, we should be able to get unique combinations. I checked only for the #1 and #2.

Night #1:

Night #2 (Downward permutation of first square)

Night #3: (Diagonal permutation of either first square or second square, take your pick)

Night #4: (Skip a row diagonal permutation)

Night #5: (Sloped diagonal permutation)

Thank you very much.

I knew there had to be a way, I just couldn't get my head around it.

Reading this carefully, I realized that this didn't work (#1 and #G plays twice on night 3 and 4).

I then tried a different approach-

Using the same first square, you should take a pen and cross out one line for #1 then do this in manner like this:

Original square:

Cross out the hortizional line
To give us the first group:

Now cross downward:

To give us the next group:

Now diagnoal:
for the group:
We can do this less or more arbitarily now, but to keep things consistent we want to try and select one from each column and one from each row, so we cross out E, 7 C:

To yield the group:
This then leaves us with only those left:


If I'm not mistaken, we now have five groups for player #1. We need to figure out the other three groups, using player 2, 3, and 4 as the lead and repeat the steps (and I *believe* by using same permutations with different leading number will yield unique results overall but I'm not enough of a mathematician to prove otherwise). This should again give us unique combinations, though we should make sure to eliminate the groups that #1 already has selected.

Hi -

Has this gone any further? I find it a fascinating

problem. I've written code that

a. Labels each of the 16 players as letters 'A' - 'P'

b. Created a Cartesian product (120 records) of all

non-duplicate combinations of the letters. (no 'AA')

c. Based on a query of the Cartesian product, produced

a table of all 4-person combinations, no dups in

any group. This resulted in 21840 records.

d. Removed all duplicate groups, e.g. 'ABCD'<-->'CBAD'

resulting in 1242 unique, non-duplicated groups.

At this point, I'm kind of at a loss based on this requirement

Over the 5 nights, each player must play each other player once.
Players may not play the same player twice.

Click to expand...

Given that there four groups x five nights = 20 competitions
and every player is involved in every competition...

Based on the above criteria, I question whether it's even possible
since in every competition every one of the 16 players is a member of a group.

Would love to know if there's any clarification of the criteria.

I am hopefully waiting on some responses to
http://www.access-programmers.co.uk/forums/showthread.php?t=152693
Need to find a way to indicate that a particularly grouping has
already been used. Thought a yes/no field might be the way but
haven't found a way to include a yes/no field in a 'Create Table'
statement.

Will post the code when I can find a way to accomplish the above.
To this point, the code processes, up to the 1242 unique records,
in about 3 seconds.

Would sure welcome any thoughts.


Best Wishes - Bob

Raskew, I actually thought about whether it can be done in five night, but after thinking about it, it is right.

See, 1 player is supposed to play each one exactly once, right? IF there's 16, then there's 15 opponents to play with. Divide by five nights, and that gives us 3 opponents.

3 opponents + 1 player = 4 player in a group!

Does seem counterintuitive, but it's really a different way of looking at the numbers.

Thanks for you assistance.

Banana - I regret your suggestion falls apart at the fourth rotation. Using a 4 x 4 table, conflicts are unavoidable at this point. No matter what method you use, someone has to play someone they have already played.

Raskew - your approach sounds promising except for one thing. I have no idea what a Cartesian product is (math is not my strong point). If you could send me the database you are using or a few directions on how it operates., I may be able to work out a solution.

Of couse, based on the restrictions there may not be a solution. It just seemed to me to be a unique method of going about it.

Again, many thanks

Statsman, which suggestion were you referring to, the first one, which I belatedly realized conflicts or the second one where I told to "cross a line"?

Banana said:

Statsman, which suggestion were you referring to, the first one, which I belatedly realized conflicts or the second one where I told to "cross a line"?

Click to expand...

Sorry, the second one (if I understood it correctly).
The first line of the fourth rotation works. The second third and fourth have conflicts.

Hmm, was sure it'd work.

I'll work it out when I get home.

Sorry to disappoint you.

Banana said:

Hmm, was sure it'd work.

I'll work it out when I get home.

Sorry to disappoint you.

Click to expand...

No disappointment.
This problem has really got to me now and it's becoming a challenge.
The only thing I know is that I won't be able to solve it on my own.

They are now talking about running it out of four different locations with each player only playing once at each venue.
I told them to forget about that until we solve the first problem.

Raskew

Did a google on Cartesian product.
Way above my limited intellect.
Is it possible to do this in an Excel spreadsheet?

In this case, have a table with just one field(tbl Lets, field Let) Populated with letters A - P (representing 16 players. If, in a query, you pull down the table twice, selecting the one field from each, and have no join between the two tables, it'll return every combination of the letters. Ala, cartesian product. Looks like this (with a little added to eliminate dups ('AA') and to assign a numerical value to each combination.).

Still struggling with this. It's a great problem.

Bob

So am I.

I now understand why my 4x4 squares didn't work- it works for player 1, 2, 3, 4 but the pairwise comparsion between other players fails. I remember when I was a young lad, there was a article for riddles which used similar techniques, but obviously memory is failing me.


Maybe some help for either of you, raskew and statsman.

I reasoned that if each player can only play one player once, it then follows that every pair in any given group must be unique.

It then follows that each pair can be grouped together (e.g. AB + CD), but only once for each one of player. IOW, we cannot have a group ABCD and ABCE or even ABFG. So therefore, we could use a list of pairs then construct groups by picking only one pair between a player or something like that.

This yields only 120 possible pairs:

Given that we want fours groups on five nights, it stands to reason that only 40 pairs out of the 120 is truly essential for creating gloablly unique pair. How to select that pair... ???

Some more information.

As I said, any group must satisfy the pairwise comparison criteria before we can accept this group.

Any given group of four has six different pairs. Thus, it is not enough to just cross out "01" and "23" for the group "0123". We must also cross out "02", "03", "12", "13" to guarantee that any other group do not ever claim those pairs which are spoken for.

At rate of taking away 6 pairs per group, of which only 2 pairs are actually used and 4 cast aside in a bin, we can generate up to 20 unique groups.

Therefore, I, with cautious optimism, hope that by going through that list, crossing out 6 pairs for each group created, we will be able to identify the 40 pairs needed to create the groups that will satisfy the pairwise comparison criteria without selecting one of 80 pairs that will violate the same criteria.

Did that help?

OK, we've got 120 unique pairs with no duplicates. When we combine two sets of these 120 pairs,
the result is 21,840 groups of four players. Eliminating all duplicate groups ('ABCD'<-->'BCAD'), results in 1242 truly unique groups.

This is where I'm at at the moment. The strategy, which I'm in the processing of coding, is to have two tables. Table1 contains the 1242 groups, Table2 contains a single field with 16 records populated with letters A - P, representing the 16 players.

The process is to:

a. Randomly select a group from table 1, store to a 20 element array.
b. Identify all possible pairs using the letters in the selected group. There will be six , e.g., Group ABCD contains AB, AC, AD, BC, BD, CD.
c. Delete from Table1 all groups containing any of the possible pairs.
d. Delete from Table2 all letters contained in the selected group.
e. Randomly select a group from Table1 that contains only letters from the remaining letters in Table2.
f. Repeat items b - d.
g. The above should run for up to 20 total repetitions, returning N groups containing all of the letters (players), with no players competing against another player more than once. Once all the letters are exhausted from
Table2, restore the original table2 to 16 letters and continue for 20 - N repetitions.
h. The problem is that there needs to be 20 groups (4 players X 5 nights) and no player should play another player more than once. It remains to be seen whether this is possible, or if at some point prior to 20, Table1 is
reduced to 0.

I'm attaching db5.mdb. It's written in A97 but should convert to later versions without problem. It consists entirely of code (Module1) with the exception of Query2 (a Make Table query), which I haven't yet been able to
reproduce in code error free. To see it in action, from the immediate (debug window) type call runem<enter>. This will call the various functions/sub, creating the tables and bringing you to the point of
the 1242 unique groups (tblSample).

Bob

Raskew

Got your database. We appear to be halfway there.
I think I will try running a query off the new table and see if that will give us the four unique per line.

I will keep you informed.

Hi -

While you can get four unique groups per line without problem, you'll need to account for your rules:

1. Over the 5 nights, each player must play each other player once.

2. Players may not play the same player twice.


Given that, it becomes a little more complex.


Best Wishes - Bob

Playing with it a bit on Excel spreadsheet. I decided to do it heuristically in hopes to give me a better insight.

I learned this:

It's basically like playing Tic-Tac-Toe. You remember them? Stupidest game ever. Assuming that both players were equally intelligent, the player who follows always have to move "forced"; e.g. he puts down X solely to block his opponent's O, rather than putting to set up for a row in line and this works against him, either ending in a defeat (if his opponent can construct a pattern where two rows can be created regardless of which they put the piece) or more likely, a draw.

It seems to me that you cannot just go around selecting pairs willy-nilly. Even with removing six pairs per group, the selection process has large implications.

Suppose we had a group '0123' and a group '4567' We already know that we take away the pair 01, 02, 03, 12, 13, and 23 for the first group, then remove 45, 46, 47, 56, 57, 67. But it's not enough because there are still otherwise valid pairs that are now constrained by the two groups: e.g. 04, 05, 06, 07, 14, 15, 16, 17, 24, 25, 26, 27, 34, 35, 36, 37. We no longer can select say, 34 and 27, though they are not removed from the available pool based on the selection of group 0123 and 4567 because to do so would violate either group. Both pair 34 and 27 would have to be paired with any other pair not in the set to satisfy the new constraint.

As we progress through the groups, the constraints increases until one bad formed group can throw wrench in the whole machinery.

Therefore, every time we create a group, we must consider the sets of pairs now constrained by the group and ensure that each of the pair in that set is not ever paired with another pair in the same set.

I'm sure this is like Rubik's cube, though... At the end of day, we'll be doing slaps on our forehead and exclaim, "Why didn't we thunk of that?!?"


Edit: Maybe a idea.

If we have a set of 120 pairs, we would create a pair of groups, throw out the 12 pairs (6 per group), then set aside the 16 constrained pairs (created by the pair of group) from the available pool and store them in a set, separate. We then repeat the process until there are none left in the pool, each pair of group having their own set of constrained pairs. (If my calculation are right, we can only get four groups with 8 leftover pairs not used or constrained at all. I'd treat those 8 pairs as particularly valuable, especially close to end.

Turning to the constrained pairs, we would have 4 sets containing 16 pairs each, for total of 64 pairs. We can create 2 more groups with 6 leftover pairs. Those 6 leftover should be in their own set.

I think I've elaborated quite enough.

We then turn our attention to each set constrained by a given pair of group. We then pair up one pair from one set with a pair from another set created by a different pair of group to ensure that we do not violate the constraints created by the first group. Of course, this will further create even more constraints, but as long we continue to select pairs that are not in same set, it will sort itself out in the end.


OMG, I think I better step away from the problem for night. See what a good night of sleep do for me...

Hi -

Personally think you've got it wrong. If you're 'B' in group ABCD, you're playing against AC & D, nobody else. In yours and each of the other groups, a particular player is competing only against the members of his/her group. The other groups just happen to be competing at the same time, but not against you. In the strategy I described, each possible combination, in each group, is removed so that it can't be used again. Don't see the logic of removing AE because you have groups ABCD and EFGH -- AE is still a viable combination.

Could well by wrong but, in my opinion, you've over-complicated the problem.

Still stuggling.

Bob