Generate teams /w highest changing no. of players
From: Daniel Lidstrom (daniel_at_c193-150-217-25.cm-upc.chello.se)
Date: 08/31/04
- Previous message: Will Twentyman: "Re: writing a Bot for battlenet chat"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 31 Aug 2004 18:41:51 +0200
Hi,
I have a list of teams, like this:
TEAM 1 TEAM 2
Björn Daniel Kim | Per Stefan Tobbe
Björn Daniel Per | Kim Stefan Tobbe
Björn Daniel Stefan | Kim Per Tobbe
Björn Daniel Tobbe | Kim Per Stefan
Björn Kim Per | Daniel Stefan Tobbe
Björn Kim Stefan | Daniel Stefan Tobbe
Björn Kim Tobbe | Daniel Per Stefan
Björn Per Stefan | Daniel Kim Tobbe
Björn Per Tobbe | Daniel Kim Stefan
Björn Stefan Tobbe | Daniel Kim Per
I have generated all possible combinations of teams consisting of
these players. Now I would like to sort the teams so that the number
of changing players from one team setup to the next is as much as
possible, in this case 2. For example, my friends and I use this
`schedule' when we play a game against each other. But I don't want to
be on the same team as a player I just played with. So when Björn,
Daniel, and Kim have played against Per, Stefan, and Tobbe, I want
the next round to consist of teams where 2 players have changed. One
such combination could be Björn, Per, Stefan vs Daniel, Kim, Tobbe. If
I have the terminology right, what I mean is that the Hamming distance
should be as high as possible between all combinations of teams. The
above list of teams is `optimal' in my sense if we order them like
this:
Björn Daniel Kim | Per Stefan Tobbe
Björn Per Stefan | Daniel Kim Tobbe
Björn Daniel Tobbe | Kim Per Stefan
Björn Kim Per | Daniel Stefan Tobbe
Björn Stefan Tobbe | Daniel Kim Per
Björn Daniel Per | Kim Stefan Tobbe
Björn Kim Stefan | Daniel Stefan Tobbe
Björn Per Tobbe | Daniel Kim Stefan
Björn Daniel Stefan | Kim Per Tobbe
Björn Kim Tobbe | Daniel Per Stefan
With this ordering, each team is guaranteed to consist of different
players after each round so to speak, and the Hamming distance would
be 2. Now to my question: how can I generate the best list of teams,
given my criterion? I already have a solution, but it is unfortunately
O(n!) I believe. What I do is this: generate all possible team setups,
in alphabetical ordering (just like the first listing above). I can do
this fairly quickly. Now is the problem. For the team setups, go
through all orderings (for 10 team setups this is 10!, right?). For
each ordering, calculate the average of the number of changing players
between each team setup. At most, this can be 2 when we have 3
players/team. Now we know the highest average `spread' as I call
it. At this point, go through all orderings again, and stop when we
have an ordering that has this spread. Now we're done. If this is as
unclear as mud, let me know, maybe I can clarify. Anyway, is there a
better algorithm? With better I mean one that is not exponential.
Thanks!
-- Daniel
- Previous message: Will Twentyman: "Re: writing a Bot for battlenet chat"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
