sharing/swapping items between lists

[Ross]

I'm trying to design an iterator that produces two lists. The first
list will be a list of unique pairings and the second will be a list
of items that weren't used in the first list. After each round, the
items that weren't used in the round before will get put back in and
the second list will be populated with unique items. To clarify,
here's an example of what my output would be if I had 8 items:

First Iteration

LIST 1 LEFTOVERS LIST

[(1,2),(3,4),(5,6)] [7,8]

Second Iteration

[(1,3), (2,7),(4,8)] [5,6]

Third Iteration

[(1,5), (2,6), (7,8)] [3,4]

etc

Additionally, I want the items in the "leftovers" list to be used the
same amount.

Can you guys suggest an approach to this problem...I'm trying to teach
myself python so an outline of how to approach this would probably be
more helpful to me than an explicit solution. I'll cry mercy if I
can't figure it out after your hints.

 

[Paul Rubin]

Can you guys suggest an approach to this problem...I'm trying to teach
myself python so an outline of how to approach this would probably be
more helpful to me than an explicit solution. I'll cry mercy if I
can't figure it out after your hints.

Look at the "set" datatype. Think of making some sets of integers
and finding their unions and intersections as appropriate.

 

[Aahz]

I'm trying to design an iterator that produces two lists. The first
list will be a list of unique pairings and the second will be a list
of items that weren't used in the first list. After each round, the
items that weren't used in the round before will get put back in and
the second list will be populated with unique items.

How do you specify what goes into the first list? Based on your
description, I would have expected that the output from the first
iteration would be

( [(1,2),(3,4),(5,6)], [7,8] )

Regardless of the actual algorithm, if you are returning items one at a
time and maintaining state in a computation, you probably want to use a
generator.

 

[Ross]

I'm trying to design an iterator that produces two lists. The first
list will be a list of unique pairings and the second will be a list
of items that weren't used in the first list. After each round, the
items that weren't used in the round before will get put back in and
the second list will be populated with unique items.

How do you specify what goes into the first list?  Based on your
description, I would have expected that the output from the first
iteration would be

( [(1,2),(3,4),(5,6)], [7,8] )

Regardless of the actual algorithm, if you are returning items one at a
time and maintaining state in a computation, you probably want to use a
generator.

I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?

 

[Aahz]

I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?

How about Googling for "round robin algorithm python"? ;-)

 

[Ross]

I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?

How about Googling for "round robin algorithm python"?  ;-)

I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.

 

[Aaron Brady]

How do you specify what goes into the first list?  Based on your
description, I would have expected that the output from the first
iteration would be

( [(1,2),(3,4),(5,6)], [7,8] )

Regardless of the actual algorithm, if you are returning items one at a
time and maintaining state in a computation, you probably want to use a
generator.

Why is this newsgroup different from all other newsgroups?

I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?

Take 3 people, 1 court.

a, b -- c
a, c -- b
b, c -- a

Take 4 people, 1 court.

a, b -- c, d
c, d -- a, b
a, c -- b, d
b, d -- a, c

Take 4 people, 2 courts.

ab, cd
ac, bd
ad, bc

Take 5 people, 1 court.

ab - cde
cd - abe
ae - bcd
bc - ade
de - abc

ac - bde
bd - ace
ce - abd
ad - bce
be - acd

You can work more by hand and post them if you want. There are known
ways to produce the list on the left out of order. It might take
multiple steps, that is, choose 2 then 2 more, instead of just choose
4. Then, you need to arrange it so the player with most court time
has at most one more match than the player with the least court time,
after each week. We could help with that too. Something tells me
there's a regular expression for it.

Do you need to account for newcomers after the rotation has started,
departers, favorites, skill, etc.?

 

[Aaron Brady]

On Apr 11, 1:10 pm, (e-mail address removed) (Aahz) wrote:

I'm trying to design an iterator that produces two lists. The first
list will be a list of unique pairings and the second will be a list
of items that weren't used in the first list. After each round, the
items that weren't used in the round before will get put back in and
the second list will be populated with unique items.
How do you specify what goes into the first list?  Based on your
description, I would have expected that the output from the first
iteration would be
( [(1,2),(3,4),(5,6)], [7,8] )
Regardless of the actual algorithm, if you are returning items one at a
time and maintaining state in a computation, you probably want to use a
generator.

I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?

Take 3 people, 1 court. snip

Then, you need to arrange it so the player with most court time
has at most one more match than the player with the least court time,
after each week.

This is the difficult constraint to satisfy.

Do you need to account for newcomers after the rotation has started,
departers, favorites, skill, etc.?

This problem was actually more difficult than I gave it credit for.

The problem first shows up in 6 players 2 courts:

abcd
efac
bd EF!

Here, E and F are playing eachother twice in a row, although everyone
is getting the right number of games as early as possible. It would
take some clever foresight, backtracing, or recognition to mix it up
better. <attempted handoff>

 

[Aahz]

I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?

How about Googling for "round robin algorithm python"? ;-)

I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.

You'll need to give us more information, then. Why don't you start with
the core algorithm you're using?

 

[Ross]

I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?
How about Googling for "round robin algorithm python"? ;-)

I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.

You'll need to give us more information, then.  Why don't you start with
the core algorithm you're using?

Here's the core algorithm I'm using:
if len(teams)%2:
teams.append(None)
mid = len(teams) //2
for i in range(rounds):
yield zip(teams[:mid], teams[mid:])
teams = teams[0:1] + teams[mid:mid+1] + teams[1:mid-1]+teams[mid
+1:]+teams[mid-1:mid]

rounds = 15
teams = range(16)
for round in round_robin(teams,rounds):
print round

 

[Ross]

On Apr 13, 9:08=A0am, (e-mail address removed) (Aahz) wrote:
com>,
I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?
How about Googling for "round robin algorithm python"? ;-)
I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.

You'll need to give us more information, then.  Why don't you start with
the core algorithm you're using?

Why is this newsgroup different from all other newsgroups?

Here's the core algorithm I'm using:

        if len(teams)%2:
                teams.append(None)
        mid = len(teams) //2
        for i in range(rounds):
                yield zip(teams[:mid], teams[mid:])
                teams = teams[0:1] + teams[mid:mid+1] + teams[1:mid-1]+teams[mid
+1:]+teams[mid-1:mid]

        rounds = 15
        teams = range(16)
        for round in round_robin(teams,rounds):
                print round

fyi rounds=15 and teams =range(16) was just test code I was playing
around with...they could theoretically be anything.

 

[Aaron Brady]

On Apr 14, 5:57 am, (e-mail address removed) (Aahz) wrote:

On Apr 13, 9:08=A0am, (e-mail address removed) (Aahz) wrote:
com>,
I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?
How about Googling for "round robin algorithm python"? ;-)
I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.
You'll need to give us more information, then.  Why don't you start with
the core algorithm you're using?

Here's the core algorithm I'm using:

        if len(teams)%2:
                teams.append(None)
        mid = len(teams) //2
        for i in range(rounds):
                yield zip(teams[:mid], teams[mid:])
                teams = teams[0:1] + teams[mid:mid+1] + teams[1:mid-1]+teams[mid
+1:]+teams[mid-1:mid]

if __name__== '__main__':

        rounds = 15
        teams = range(16)
        for round in round_robin(teams,rounds):
                print round

fyi rounds=15 and teams =range(16) was just test code I was playing
around with...they could theoretically be anything.

Here is an idea. Create a list of all possible pairs, using
itertools.combinations. You'll notice everyone gets equal play time
and equal time against each other on a pair-by-pair basis. Then, call
random.shuffle until one player isn't playing on two courts in one
day.

It has the disadvantage that you might end up with player A playing
lots early on and rarely at the end, and B rarely early on and lots at
the end. Perhaps you could generate a few to several correct
solutions, then choose the most evenly distributed. Does this make
sense?

 

[Aaron Brady]

On Apr 14, 5:57 am, (e-mail address removed) (Aahz) wrote:

On Apr 13, 9:08=A0am, (e-mail address removed) (Aahz) wrote:
com>,
I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?
How about Googling for "round robin algorithm python"? ;-)
I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.
You'll need to give us more information, then.  Why don't you start with
the core algorithm you're using?
--
Aahz ([email protected])           <*>        http://www.pythoncraft.com/
Why is this newsgroup different from all other newsgroups?
Here's the core algorithm I'm using:
def round_robin(teams,rounds):
        if len(teams)%2:
                teams.append(None)
        mid = len(teams) //2
        for i in range(rounds):
                yield zip(teams[:mid], teams[mid:])
                teams = teams[0:1] + teams[mid:mid+1] + teams[1:mid-1]+teams[mid
+1:]+teams[mid-1:mid]
if __name__== '__main__':
        rounds = 15
        teams = range(16)
        for round in round_robin(teams,rounds):
                print round

fyi rounds=15 and teams =range(16) was just test code I was playing
around with...they could theoretically be anything.

Here is an idea.  Create a list of all possible pairs, using
itertools.combinations.  You'll notice everyone gets equal play time
and equal time against each other on a pair-by-pair basis.  Then, call
random.shuffle until one player isn't playing on two courts in one
day.

This might take a long time. Not that I can guarantee that a depth-
first-search would be any faster, or that a breadth-first-search would
run faster *and* run in available memory. <cough>

 

[Ross]

On Apr 14, 5:57 am, (e-mail address removed) (Aahz) wrote:

On Apr 13, 9:08=A0am, (e-mail address removed) (Aahz) wrote:
com>,
I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?
How about Googling for "round robin algorithm python"? ;-)
I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.
You'll need to give us more information, then.  Why don't you start with
the core algorithm you're using?
--
Aahz ([email protected])           <*>        http://www.pythoncraft.com/
Why is this newsgroup different from all other newsgroups?
Here's the core algorithm I'm using:
def round_robin(teams,rounds):
        if len(teams)%2:
                teams.append(None)
        mid = len(teams) //2
        for i in range(rounds):
                yield zip(teams[:mid], teams[mid:])
                teams = teams[0:1] + teams[mid:mid+1] + teams[1:mid-1]+teams[mid
+1:]+teams[mid-1:mid]
if __name__== '__main__':
        rounds = 15
        teams = range(16)
        for round in round_robin(teams,rounds):
                print round
fyi rounds=15 and teams =range(16) was just test code I was playing
around with...they could theoretically be anything.

Here is an idea.  Create a list of all possible pairs, using
itertools.combinations.  You'll notice everyone gets equal play time
and equal time against each other on a pair-by-pair basis.  Then, call
random.shuffle until one player isn't playing on two courts in one
day.

This might take a long time.  Not that I can guarantee that a depth-
first-search would be any faster, or that a breadth-first-search would
run faster *and* run in available memory.  <cough>

I have a sub-optimal solution that I'm playing with now. Since my
output is a list of tuples and looks something like this (if there
were 16 teams and 15 rounds), I could designate a each nth tuple in
each round as a bye, but since the 1st item in my list remains fixed,
it's suboptimal. For example, you could say every 4th (and/or 3rd ,
5th, etc depending on how many available cts) tuple in each round gets
a bye and pop() it from the list...:

[(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15)]
[(0, 9), (8, 10), (1, 11), (2, 12), (3, 13), (4, 14), (5, 15), (6, 7)]
[(0, 10), (9, 11), (8, 12), (1, 13), (2, 14), (3, 15), (4, 7), (5, 6)]
[(0, 11), (10, 12), (9, 13), (8, 14), (1, 15), (2, 7), (3, 6), (4, 5)]
[(0, 12), (11, 13), (10, 14), (9, 15), (8, 7), (1, 6), (2, 5), (3, 4)]
[(0, 13), (12, 14), (11, 15), (10, 7), (9, 6), (8, 5), (1, 4), (2, 3)]
[(0, 14), (13, 15), (12, 7), (11, 6), (10, 5), (9, 4), (8, 3), (1, 2)]
[(0, 15), (14, 7), (13, 6), (12, 5), (11, 4), (10, 3), (9, 2), (8, 1)]
[(0, 7), (15, 6), (14, 5), (13, 4), (12, 3), (11, 2), (10, 1), (9, 8)]
[(0, 6), (7, 5), (15, 4), (14, 3), (13, 2), (12, 1), (11, 8), (10, 9)]
[(0, 5), (6, 4), (7, 3), (15, 2), (14, 1), (13, 8), (12, 9), (11, 10)]
[(0, 4), (5, 3), (6, 2), (7, 1), (15, 8), (14, 9), (13, 10), (12, 11)]
[(0, 3), (4, 2), (5, 1), (6, 8), (7, 9), (15, 10), (14, 11), (13, 12)]
[(0, 2), (3, 1), (4, 8), (5, 9), (6, 10), (7, 11), (15, 12), (14, 13)]
[(0, 1), (2, 8), (3, 9), (4, 10), (5, 11), (6, 12), (7, 13), (15, 14)]

 

[Aaron Brady]

On Apr 14, 5:57 am, (e-mail address removed) (Aahz) wrote:

On Apr 13, 9:08=A0am, (e-mail address removed) (Aahz) wrote:
com>,
I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?
How about Googling for "round robin algorithm python"? ;-)
I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.
You'll need to give us more information, then.  Why don't you start with
the core algorithm you're using?
--
Aahz ([email protected])           <*>        http://www.pythoncraft.com/
Why is this newsgroup different from all other newsgroups?
Here's the core algorithm I'm using:
def round_robin(teams,rounds):
        if len(teams)%2:
                teams.append(None)
        mid = len(teams) //2
        for i in range(rounds):
                yield zip(teams[:mid], teams[mid:])
                teams = teams[0:1] + teams[mid:mid+1] + teams[1:mid-1]+teams[mid
+1:]+teams[mid-1:mid]
if __name__== '__main__':
        rounds = 15
        teams = range(16)
        for round in round_robin(teams,rounds):
                print round
fyi rounds=15 and teams =range(16) was just test code I was playing
around with...they could theoretically be anything.
Here is an idea.  Create a list of all possible pairs, using
itertools.combinations.  You'll notice everyone gets equal play time
and equal time against each other on a pair-by-pair basis.  Then, call
random.shuffle until one player isn't playing on two courts in one
day.

This might take a long time.  Not that I can guarantee that a depth-
first-search would be any faster, or that a breadth-first-search would
run faster *and* run in available memory.  <cough>

I have a sub-optimal solution that I'm playing with now. Since my
output is a list of tuples and looks something like this (if there
were 16 teams and 15 rounds), I could designate a each nth tuple in
each round as a bye, but since the 1st item in my list remains fixed,
it's suboptimal. For example, you could say every 4th (and/or 3rd ,
5th, etc depending on how many available cts) tuple in each round gets
a bye and pop() it from the list...:

From what I understood, you want each player to play each other player
exactly once, with no empty courts until the last round. Your
solution doesn't achieve that if you simply omit a choice of matches,
even if you omit them fairly. How to omit them fairly is a separate
question.

I observe that your tuples follow a pattern. Each court is a match
between the first slot on the previous court on the previous week, and
the second slot on the previous court on the next week, with the
exceptions of the first and last courts. The same player always plays
on court one against the second slot on the second court on the
previous week (and hence (?), first slot on second court on the next
week), and the last court is always between the second slot on the
last court on the next week and the first slot on the previous court
on the previous week. IN other words, it follows a zig zag.

Your idea of omitting a given court, including the last but except the
first, omits each player twice, and two opponents of each player.

If you try to finish the schedule, it will take at least three more
weeks. Arranging the second column:

5, 3
14, 7
10, 12
2, 8
6, 4
13, 15
9, 11

11, 13
15, 6
4, 2
8, 10
12, 14
7, 5
3, 1

1, 9

There is guaranteed to be one left over. From what I read about your
algorithm last night, if the number of teams is odd, you might be able
to finish in two more weeks, because there is always a 'None', but I
haven't tried it.

Something tells me that my 'randomly permute and eliminate impossible
rounds' won't be any more successful, except if you have fewer courts
than num*(num+1)/2, but I can give it a shot.

 

[samwyse]

Here is an idea.  Create a list of all possible pairs, using
itertools.combinations.  You'll notice everyone gets equal play time
and equal time against each other on a pair-by-pair basis.  Then, call
random.shuffle until one player isn't playing on two courts in one
day.

It has the disadvantage that you might end up with player A playing
lots early on and rarely at the end, and B rarely early on and lots at
the end.  Perhaps you could generate a few to several correct
solutions, then choose the most evenly distributed.  Does this make
sense?

Here's my idea: generate all possible pairs:

import itertools
players = [chr(c) for c in xrange(ord('a'),ord('z')+1)]
all_pairs = list(itertools.combinations(players,2))

partition the list: chosen, leftover, used = list(), list(), list()
for p in pairs:
a, b = p
if a in used or b in used:
leftover.append(p)
else:
chosen.append(p)
used.append(a)
used.append(b)
return chosen, leftover
print 'week', week+1
this_week, pairs = choose_nonoverlapping(pairs)
print ', '.join(map(lambda t: ' vs '.join(t), this_week
[:court_count]))
pairs[0:0] = this_week[court_count:]


week 1
a vs b, c vs d, e vs f, g vs h, i vs j, k vs l, m vs n, o vs p, q vs
r, s vs t
week 2
u vs v, w vs x, y vs z, a vs c, b vs d, e vs g, f vs h, i vs k, j vs
l, m vs o
week 3
n vs p, q vs s, r vs t, a vs d, b vs c, e vs h, f vs g, i vs l, j vs
k, m vs u
week 4
o vs v, w vs y, x vs z, a vs e, b vs f, c vs g, d vs h, i vs m, j vs
n, k vs p
week 5
l vs q, r vs s, t vs u, a vs f, b vs e, c vs h, d vs g, i vs n, j vs
m, k vs o
week 6
p vs v, w vs z, x vs y, a vs g, b vs h, c vs e, d vs f, i vs o, j vs
q, k vs m
week 7
l vs n, r vs u, a vs h, b vs g, c vs f, d vs e, i vs p, j vs o, k vs
q, m vs s
week 8
t vs v, a vs i, b vs j, c vs k, d vs l, e vs m, f vs n, g vs o, h vs
p, q vs u
week 9
r vs w, s vs x, a vs j, b vs i, c vs l, d vs k, e vs n, f vs m, g vs
p, h vs o
week 10
q vs t, u vs y, v vs z, a vs k, b vs l, c vs i, d vs j, e vs o, f vs
p, g vs m

 

[Aaron Brady]

Here is an idea.  Create a list of all possible pairs, using
itertools.combinations.  You'll notice everyone gets equal play time
and equal time against each other on a pair-by-pair basis.  Then, call
random.shuffle until one player isn't playing on two courts in one
day.

It has the disadvantage that you might end up with player A playing
lots early on and rarely at the end, and B rarely early on and lots at
the end.  Perhaps you could generate a few to several correct
solutions, then choose the most evenly distributed.  Does this make
sense?

Here's my idea:  generate all possible pairs:

import itertools
players = [chr(c) for c in xrange(ord('a'),ord('z')+1)]
all_pairs = list(itertools.combinations(players,2))

partition the list:>>> def choose_nonoverlapping(pairs):

        chosen, leftover, used = list(), list(), list()
        for p in pairs:
                a, b = p
                if a in used or b in used:
                        leftover.append(p)
                else:
                        chosen.append(p)
                        used.append(a)
                        used.append(b)
        return chosen, leftover

        print 'week', week+1
        this_week, pairs = choose_nonoverlapping(pairs)
        print ', '.join(map(lambda t: ' vs '.join(t), this_week
[:court_count]))
        pairs[0:0] = this_week[court_count:]

snip

Your idea arrives at a sub-optimal solution on players= 'abcdef',
court_count= 3.

Correct, by hand (5 weeks):

ab cd ef
ac be df
ad ce bf
ae bd cf
af bc de

Program (7 weeks):

week 1
a vs b, c vs d, e vs f
week 2
a vs c, b vs d
week 3
a vs d, b vs c
week 4
a vs e, b vs f
week 5
a vs f, b vs e
week 6
c vs e, d vs f
week 7
c vs f, d vs e

However, you do correctly arrive at all the combinations, in better
than the naive 'one pair per week' solution. Further, you produced
the correct solution for players= 'abcdef', for court_count= 1 and
court_count= 2, which I also tested. Damage report?

 

[Aaron Brady]

On Apr 14, 5:57 am, (e-mail address removed) (Aahz) wrote:

On Apr 13, 9:08=A0am, (e-mail address removed) (Aahz) wrote:
com>,
I'm sorry...my example was probably a bad one. A better example of
output I would like would be something like [[1,2],[3,4],[5,6]] and
then for the leftovers list [7,8,9,10 etc]. What I'm trying to do is
produce some sort of round robin algorithm for tennis that is
constrained by the number of courts available each week. So if there
are only 3 courts available for a singles league and 10 people have
signed up, 4 players will have a bye each week. I want my algorithm to
produce unique matchups each week and also give each player the same
angle?
How about Googling for "round robin algorithm python"? ;-)
I have the basic algorithm and it works fine...I'm just having trouble
adding another parameter to it that allows for court constraints and
bye weeks.
You'll need to give us more information, then.  Why don't you start with
the core algorithm you're using?
--
Aahz ([email protected])           <*>        http://www.pythoncraft.com/
Why is this newsgroup different from all other newsgroups?
Here's the core algorithm I'm using:
def round_robin(teams,rounds):
        if len(teams)%2:
                teams.append(None)
        mid = len(teams) //2
        for i in range(rounds):
                yield zip(teams[:mid], teams[mid:])
                teams = teams[0:1] + teams[mid:mid+1] + teams[1:mid-1]+teams[mid
+1:]+teams[mid-1:mid]
if __name__== '__main__':
        rounds = 15
        teams = range(16)
        for round in round_robin(teams,rounds):
                print round
fyi rounds=15 and teams =range(16) was just test code I was playing
around with...they could theoretically be anything.
Here is an idea.  Create a list of all possible pairs, using
itertools.combinations.  You'll notice everyone gets equal play time
and equal time against each other on a pair-by-pair basis.  Then, call
random.shuffle until one player isn't playing on two courts in one
day.

This might take a long time.  Not that I can guarantee that a depth-
first-search would be any faster, or that a breadth-first-search would
run faster *and* run in available memory.  <cough>

I have a sub-optimal solution that I'm playing with now. Since my
output is a list of tuples and looks something like this (if there
were 16 teams and 15 rounds), I could designate a each nth tuple in
each round as a bye, but since the 1st item in my list remains fixed,
it's suboptimal. For example, you could say every 4th (and/or 3rd ,
5th, etc depending on how many available cts) tuple in each round gets
a bye and pop() it from the list...:

<multiposting>
The randomizing solution isn't quite suitable for 16 teams. With 5
teams/1 court, and 5 teams/2 courts, 6 teams/2 courts, the solution
comes within seconds. For 7 teams/3 courts, the solution takes a few
minutes. (1 GHz.) Here's the code. I doubt it's adequate, but it
still could be faster, and is definitely less stressful, than by
hand. For any long-running calculations, save your results.

from itertools import combinations, permutations
import string
import random as ran
def circulate( num_players, num_courts ):
''' 2 players per court '''
assert num_players<= 26, '26 players max'
assert num_players> 2* num_courts, 'no randomization needed'
player_set= set( string.ascii_lowercase[ :num_players ] )
combs= list( ''.join( x ) for x in combinations( player_set, 2 ) )

#print( len( list( permutations( combs ) ) ) )

iteration= 0
while 1:
ran.shuffle( combs )
#print( combs )
ok= True
for i in range( 0, len( combs ), num_courts ):
cur= ''.join( combs[ i: i+ num_courts ] )
#print( cur )
if len( set( cur ) )!= len( cur ): # any dupes in round
ok= False
break
if ok:
return [ combs[ i: i+ num_courts ] for i in range( 0, len
( combs ), num_courts ) ]
iteration+= 1
if iteration & 0xFFFF== 0:
print( iteration, hex( iteration ) )

 

[samwyse]

Here's my idea: generate all possible pairs:

import itertools
players = [chr(c) for c in xrange(ord('a'),ord('z')+1)]
all_pairs = list(itertools.combinations(players,2))

partition the list:

def choose_nonoverlapping(pairs):

chosen, leftover, used = list(), list(), list()
for p in pairs:
a, b = p
if a in used or b in used:
leftover.append(p)
else:
chosen.append(p)
used.append(a)
used.append(b)
return chosen, leftover

court_count = 10
week_count = 10
pairs = all_pairs
for week in xrange(week_count):

print 'week', week+1
this_week, pairs = choose_nonoverlapping(pairs)
print ', '.join(map(lambda t: ' vs '.join(t), this_week
[:court_count]))
pairs[0:0] = this_week[court_count:]

snip

Your idea arrives at a sub-optimal solution on players= 'abcdef',
court_count= 3.

Correct, by hand (5 weeks):

ab cd ef
ac be df
ad ce bf
ae bd cf
af bc de

Program (7 weeks):
[snip]

However, you do correctly arrive at all the combinations, in better
than the naive 'one pair per week' solution. Further, you produced
the correct solution for players= 'abcdef', for court_count= 1 and
court_count= 2, which I also tested. Damage report?

It does work better when there are a limited number of courts, but
since that was in the original description, I didn't worry too much.

One could product several random shuffles of the list of combinations
and see which produced the shortest list of results. That would add
indeterminancy without guaranteeing an optimal result. But I think
that other people have algorithms for that case, so I'm not too
worried.

I've tried generalizing to competitions with more than two player
(e.g. the Pinewood Derby, where up four cars are in each heat), but
the algorithm falls apart, mostly due to the way
itertools.combinations returns its results.

 

[samwyse]

The randomizing solution isn't quite suitable for 16 teams.  With 5
teams/1 court, and 5 teams/2 courts, 6 teams/2 courts, the solution
comes within seconds.  For 7 teams/3 courts, the solution takes a few
minutes.

7 teams/3 courts is the same as 8 teams/4 courts, where the extra
player is named "bye". In other words, it's an uncontrained problem.