A tricky problem

[rhys]

I'm hoping to resolve and implement this as a stored procedure but at the
moment I simply need to understand how to resolve the problem and I might
code it in C++ first.

I have 8 football teams, I want each team to play each other team once in
forthcoming weeks and the purpose is to make bookings in a bookings table
allocating teams to facilities on a certain date.

There will need to be 4 matches over 7 weeks. What I want is a method to
implement the allocation of matches that I can then code.

warning - this is difficult.


thanks,


rhys

[Simon Sellick]

Rhys,

I think I have come up with a way of solving it - not very elegant, but I
think it would work.

I assume that each team has a facility to play on, and you aren't worried
about balancing home and away matches at present.

You need variables of some description (memory variables, arrays, objects,
rows in a table etc) to hold:

- number of teams: nTeams
- number of playing occasions: nOccasions = nTeams - 1
- number of fixtures needed: nFixtures =(nTeams * (nTeams - 1)) / 2
- for each team, number of fixtures arranged: teamFixtures[nTeams]
- for each fixture: fixtures[nFixtures]:
- the teams involved: .TeamH, .TeamA
- the occasion it is arranged for: .Occasion
- (I suppose it would be a good place to hold scores, too)

First, generate the list of possible fixtures:

for n = 0, i = 1 to nMatches - 1
for j = i + 1 to nMatches
fixtures[n].TeamH = i
fixtures[n].TeamA = j
fixtures[n].Occasion = 0

The hard bit is getting the possible fixtures allocated to teams so that
the fewest possible occasions are used. I think you can do this:

for each occasion:

(1) Search teamFixtures from the start to the end and extract t1 with the
fewest fixtures arranged. That is the team to arrange the next fixture for.


(2) Search fixtures[] from the start looking for .TeamH or .TeamA = t1 and
.Occasion = 0. That gives a candidate fixture, for the right team, that
hasn't already been arranged. For this candidate, extract the OTHER team
(teamA or teamH) t2.

(3) Search fixtures[].TeamH and .TeamA from the start for t2 with .Occasion
= current occasion. If you find it, you can't arrange this fixture for
this occasion, so continue search (2) to find another candidate.

(4) If the candidate was OK, set fixtures[].Occasion to current occasion,
and increment teamFixtures[t1] and [t2].

Repeat the above (find team, find candidate, check candidate, arrange fixture)
until you reach the end of the second search without identifying a candidate
fixture. At this point, as many matches as can be arranged for the occasion,
have been arranged.

I will try coding this over the weekend to see whether it works - but let
me know if you find a more pleasing solution!

Good luck,
Simon.

PS: sorry about the mixed syntax.

[rhys]

Simon,

Thanks for your help.

I think that you are correct that there is no simple solution to this. It
seems that the crucial approach is to iterate through potential matches testing
for and accepting valid matches i.e. matches between teams that have not
previously played each other.

There's no need for you to try coding this. I'll try when I have a chance
this weekend and send you a copy.

regards,

rhys

"Simon Sellick" <simon.sellick@tesco.net> wrote:
>
>Rhys,
>
>I think I have come up with a way of solving it - not very elegant, but
I
>think it would work.
>
>I assume that each team has a facility to play on, and you aren't worried
>about balancing home and away matches at present.
>
>You need variables of some description (memory variables, arrays, objects,
>rows in a table etc) to hold:
>
>- number of teams: nTeams
>- number of playing occasions: nOccasions = nTeams - 1
>- number of fixtures needed: nFixtures =(nTeams * (nTeams - 1)) / 2
>- for each team, number of fixtures arranged: teamFixtures[nTeams]
>- for each fixture: fixtures[nFixtures]:
> - the teams involved: .TeamH, .TeamA
> - the occasion it is arranged for: .Occasion
> - (I suppose it would be a good place to hold scores, too)
>
>First, generate the list of possible fixtures:
>
> for n = 0, i = 1 to nMatches - 1
> for j = i + 1 to nMatches
> fixtures[n].TeamH = i
> fixtures[n].TeamA = j
> fixtures[n].Occasion = 0
>
>The hard bit is getting the possible fixtures allocated to teams so that
>the fewest possible occasions are used. I think you can do this:
>
>for each occasion:
>
>(1) Search teamFixtures from the start to the end and extract t1 with the
>fewest fixtures arranged. That is the team to arrange the next fixture
for.
>
>
>(2) Search fixtures[] from the start looking for .TeamH or .TeamA = t1 and
>.Occasion = 0. That gives a candidate fixture, for the right team, that
>hasn't already been arranged. For this candidate, extract the OTHER team
>(teamA or teamH) t2.
>
>(3) Search fixtures[].TeamH and .TeamA from the start for t2 with .Occasion
>= current occasion. If you find it, you can't arrange this fixture for
>this occasion, so continue search (2) to find another candidate.
>
>(4) If the candidate was OK, set fixtures[].Occasion to current occasion,
>and increment teamFixtures[t1] and [t2].
>
>Repeat the above (find team, find candidate, check candidate, arrange fixture)
>until you reach the end of the second search without identifying a candidate
>fixture. At this point, as many matches as can be arranged for the occasion,
>have been arranged.
>
>I will try coding this over the weekend to see whether it works - but let
>me know if you find a more pleasing solution!
>
>Good luck,
>Simon.
>
>PS: sorry about the mixed syntax.

[Michael Levy]

This is not very difficult. A CROSS JOIN will get you most of the way.

CREATE TABLE team (
teamid INTEGER IDENTITY PRIMARY KEY,
name VARCHAR(30))

SELECT
t1.name, t2.name
FROM
team t1 CROSS JOIN team t2
WHERE t1.name != t2.name

If the team table contains:
A
B

This query will return
A B
B A

You just need to figure out how to remove the extra rows.

-Mike
--
Michael Levy MCDBA, MCSD, MCT
michaell@gasullivan.com
"rhys" <rhystucker@yahooo.com> wrote in message
news:3a9eb055$1@news.devx.com...