automatic "lotjes trekken"

[Tim Peters]

[Carel Fellinger]
> ...
> in the damp and cold days of late November and early December we
> think and ponder on a nice and teasing Sinterklaas gift for one-
> other. To prevent doublures, we draw lotjes (lots) with the name
> of the one to tease.  Ofcourse you are not allowed to draw one-self.
> And often some one would rather not have specific others; e.g. my
> eldest girls, being twins, rather not have each other, as the mere
> fact that one refuses to cooperate with the other is a sure sign
> that she drew her twin sister.  And part of the fun is that the
> drawing is secret and kept secret; though everybody tries to figure
> it out anyway.
>
> Being fed up with drawing and redrawing and redrawing and...
> I decided to use python.  Piece of cake using random.choice, sends
> mail to all and the lot.  Then I added these restrictions, still
> trivial. But elas running the little devil with to many restrictions
> took awile:) I decided to check before hand whether a drawing was
> possible at all by counting all possibilities. There must be something
> more clever than backtracking to get to this number, something with
> permutations and so, but my mind is to blurred to see it.

The mail<->news gateway is screwed up, so my apologies if you already got a
sufficient answer (although, as will become clear, I doubt it <wink>).

In combinatorics, this is the general problem of permutations with forbidden
positions:  you can view the lots as mapping the set of people into itself,
one-to-one and onto.  That is, it's a permutation.  Since a person is not
allowed to map to themself here, an upper bound is the number of
"derangements" (great word!) of N people.  A derangement is simply a
permutation where no element maps to itself.  Asymptotically, there are N!/e
derangements of N things (N! is N factorial = N * (N-1) * ... * 1, and e is
2.71828...).  This is an excellent approximation even for small N; e.g., for
N=5, 5!/e = 120/e ~= 44.15, while the exact number of derangements of 5
things is 44.

That the number e pops out of a very uniform special case should suggest
that the general theory isn't likely to be dirt simple.  And, in a great
surprise, it turns out that it actually isn't dirt simple <wink>.  Something
you could ponder the whole winter!

To get you started, here's a simple (& std) way to think about it:  picture
an NxN chessboard.  A permutation corresponds naturally to placing N rooks
on the chessboard in such a way that no rook can capture another.  For
example, label the rows of the chessboard with the names of the people, and
the columns likewise, and say that a rook in rank i and file j (row i and
column j) means that person i has drawn person j.  No two rooks can be in
the same row (a person can't get gifts for two people) or in the same column
(a person can't get gifts from two people).

A permutation with forbidden positions is then placing N non-capturing rooks
on a *damaged* chessboard, where large irregular lumps of hardened smelly
cheese are firmly stuck to forbidden squares, thus preventing a rook from
standing on them.  For example, the derangement requirement is modeled by
placing cheese all along the main diagonal.

Now you *can* systematically count the number of ways to do this without
backtracking, but accounting for the 2-dimensional geometry of the forbidden
positions is essential.  This makes it tricky.  Here's how:

Stare at your damaged chessboard.  Pick any square without a lump of cheese
on it (if there aren't any, you're done:  it's impossible).  You have two
choices:  you can either put a rook there, or not.  This splits all possible
solutions into two mutually exclusive kinds, so the total number of
solutions is the sum of the number of solutions for each case:

1. You do put a rook there.  Then physically remove that square's rank and
file from the chessboard, and count the number of ways to put N-1
non-capturing rooks on the resulting N-1 x N-1 chessboard.

2. You do not put a rook there.  Then firmly press a large irregular lump of
hardened smelly cheese on to the square, and count the number of ways to
place N non-capturing rooks on this cheesier N x N chessboard.

3. Add those two results.

This reduces the problem to two subproblems of the same kind, but each
subproblem either has a smaller board to worry about or a board with more
cheese.  So proceed recursively, and every path eventually leads to a 1x1
board and/or a board completely filled with cheese.  Those are trivial.

Here's the depressing part:  the end cases are *too* trivial.  The tails of
the recursion contribute only 0 or 1 each to the total count.  So there are
a *lot* of function calls to get those to add up to something that can grow
as large as N!/e (if you've got no restriction other than derangement).

This is where "accounting for the 2-dimensional geometry" comes into play:
at each step, you want to pick the free square with care, striving to
produce subproblems where the cheese-free squares can be split into two
smaller chessboards with no rows or columns in common.  The number of
solutions for a chessboard of that special form is the *product* of the
number of solutions for the two smaller chessboards (they have no rows or
columns in common, so what you do to one of them can have no effect on the
other), and that lets you get to the final answer enormously quicker.

The next twist in the tale is too involved to explain here:  it turns out
that it's possible to deduce the result from the numbers of ways to place 0,
1, 2, ... and N non-capturing rooks on the "cheese-inverted" chessboard
obtained by putting cheese on all the empty squares and removing the cheese
from the cheesy squares.  In most applications, there are many more empty
squares than cheesy squares, so inverting their roles can slash the amount
of computation.

If you enjoy this sort of thing, the theory is elegant and makes for a
delightfully delicate series of programming challenges (start with a Cheese
class <wink>).  I did it in Fortran once, many years ago -- and that I don't
have to anymore is the true meaning of Thanksgiving <gobble>.

sinterturkeyly y'rs  - tim