Counter for items in lists in lists?

[Alex Martelli]

Charlotte Henkle <charlotte at fgm.com> wrote:
   ...
> I was given a problem by a friend.  He is in a tennis group that has 6
> members.  They play once a week for 10 weeks.  They were having
> trouble generating a schedule that was random but fair (IE everyone
> gets to play a base number of times , and the mod is evenly and
> randomly distributed).

How many of the 6 members can play on each of those once-weekly
occasions?

> My first pass through was short and simple:  Figure out the total
> number of games that will be played, and then use something like this:
> 
> gamePlayers=random.sample(templist, players_per_game)
> 
> to fill up all the game slots.  Neat, simple.
> 
> The problem I found with this solution was that it didn't give me a
> weighted list for remainder.  The same person could get in all of the
> "extra" games.

Yep, you're being a bit "too random" there -- sampling with repetition.

Consider random.shuffle: puts the players in arbitrary order but without
repetition.  Just pick whatever number at a time, say from the back --
doing so from the front would be just as good, but slower, so it might
as well be from the back.  When you're trying to pick more players than
are left in the shuffled list you're peeling stuff from, make sure those
get in then reshuffle the original list minus those who are already in,
for the next time.

Ah, natural language is SO complicated, let's put it in pseudocode.
First, you'll need sets, since obviously there are set operations
involved (e.g., "minus those who are already in" is goofy language for a
set difference operation).  So let's make sure we have sets.  In Python
2.4, they're built-in; in 2.3, they're in module sets of the standard
library.  To ensure you run optimally in either release, star your
program with:

import random
try: set=set
except NameError: from sets import Set as set

Now we're ready to write our pseudocode.  At each step, i.e. each time
another weekly game is planned, we'll have: some list X of players who
haven't played yet in this 'round' in shuffled order; a request for N
players for tonight; and of course the original set P of players.  If N
is less than the items in X we're in an easy case:
    if N < len(X):
        yield X[-N:]
        del X[-N:]
i.e. we just yield the last N items of list X then remove those same
items from further consideration in this round.

If more players are going to play tonight, than there are items in X,
it's a little bit more complicated.  We need to prepare a shuffled list
of all players except those who are alreayd in X...:
    else:
        newX = list(P-set(X))
        random.shuffle(newX)
and then yield the contents of X and the needed N-len(X) items of newX:
        fromNewX = N-len(X)
        yield X + newX[-fromNewX:]
finally, we need to remove from newX the items we just yielded, and set
the remainder as the new value of X for the next evening of play:
        X = newX[:-fromNewX]

Great, but how do we get started?  Heh, funny, if X is empty we're just
in a starting position -- len(X) is 0 so we're gonna prepare newX, and
we're gonna prepare it from the whole of set P... just as we want.  So
all the initialization we need is to make sure that P _is_ a set and
that X is empty:
    P = set(P)
    X = []

Great -- now that we have our pseudocode, how do we turn it into actual
working code?  That's where Python shines, for the pseudocode we jotted
down to help our thinking as we reasoned about the problem IS working
Python code.  We could rename X, P and N, but apart from that, here is
the generator we need...:

def choose_players(P, N):
    assert len(P) >= N > 0
    P = set(P)
    X = []
    while True:
        if N < len(X):
            yield X[-N:]
            del X[-N:]
        else:
            newX = list(P-set(X))
            random.shuffle(newX)
            fromNewX = N-len(X)
            yield X + newX[-fromNewX:]
            X = newX[:-fromNewX]

I've added a check that N makes sense (0 or fewer players, or more than
the club's membership, being needed each time, obviously makes no
sense!) and an unending loop around the whole thing.  This is a
nonterminating generator -- it won't ever stop iterating by itself; it
needs to be called the appropriate number of times.  I find that more
useful than passing the generator a parameter telling it how many times
to loop (you'd just need to add such a parameter T and change the while
to 'for i in xrange(T):' -- but if you need to do that, you could just
as well use iterator.islice or whatever to limit the numbers of steps
over the generator...).


Here's an example use...:

for i, players in enumerate(choose_players(range(13), 4))):
    print players
    if i > 9: break

Here there are 13 members, named 0 to 12, and each week 4 can play, for
11 weeks.  You can run it a few times to eyeball it for correctness, but
of course you'll want to check it out better eventually, for example:

for number_of_tests in range(10):
    number_of_plays = 13*[0]
    for i, players in enumerate(choose_players(range(13), 4)):
        for p in players: number_of_plays[p] += 1
        if i > 9: break
    for i in range(max(number_of_plays)+1):
        print '%d:%d'%(i, number_of_plays.count(i)),
    print

You'll soon see that the results aren't as even as we wished, e.g.:

kallisti:~/downloads alex$ python2.3 pla.py 
0:0 1:0 2:2 3:4 4:7
0:0 1:0 2:1 3:6 4:6
0:0 1:0 2:0 3:8 4:5
0:0 1:0 2:0 3:8 4:5
0:0 1:0 2:2 3:4 4:7
0:0 1:0 2:1 3:6 4:6
0:0 1:0 2:1 3:6 4:6
0:0 1:0 2:0 3:8 4:5
0:0 1:0 2:0 3:8 4:5
0:0 1:0 2:0 3:8 4:5

ooops -- the 44 available 'slots' are NOT always divided "three apiece
and a fourth one for 5 lucky ones of the 13 members" -- sometimes one or
even two members play only twice!  So what's wrong with the pseudode we
had so nicely worked out...?  Hmmm, clearly the 'left over' 13th player
who first gets to play on the 4th night isn't given a chance to play
again soon enough... he should go right back into the new X.  Can we fix
that?  We can sure try, just change in the above:
            newX = list(P-set(X))
            random.shuffle(newX)
            fromNewX = N-len(X)
            yield X + newX[-fromNewX:]
            X = newX[:-fromNewX]
into:
            newX = list(P-set(X))
            random.shuffle(newX)
            fromNewX = N-len(X)
            yield X + newX[-fromNewX:]
            X += newX[:-fromNewX]
            random.shuffle(X)

Ah, NOW our tests are more satisfactory -- huge runs of
0:0 1:0 2:0 3:8 4:5
just as we wanted!  Of course, that's no mathematical _proof_ that our
procedure is correct -- indeed, it's QUITE interesting to provide such a
proof (but I have no space left in the margins of this post to do
so...:-).


I hope that by showing you how a little program can evolve in real life,
from specs to thinking in pseudocode to Python, eyeball-testing, better
testing (with counting;-), correction of some problem, ..., I may have
helped you on your way to "thinking like a programmer"!-)


Alex