automatic "lotjes trekken"

[Carel Fellinger]

Alex <alex at somewhere.around.here> wrote:

> Hi, Carel.

> This is a fun problem.  Basically, you want to find a set of disjoint
> loops in a digraph whose union contains all of the digraph's vertices.
> How big, and how far from complete, is the graph likely to be?  I don't
> know a lot of graph theory, but it seems likely that the problem of

Neither do I, I'm even not sure I understand what you wrote:)

> counting every such set of loops is NP-complete for a general graph.  At

But you're definitely right here. Though n! always looks to me as a harmless
function, something like "really n", it is almost as dreadfull as n^^n.
Fortunately in my family n is rather small, we are five now and even if the
girls get hooked we won't surpase eight for quite some time yet:) Moreover
the problem space is a little below n!, as one shouldn't draw oneself. The
question was: how much lower given some constrains.

The approach I've taken sofar was to simulate real life, let
everybody draw, and as soon as someone draws one he doesn't want,
throw all the lots back in the hat and try again. [[ well Greg, in my
books this wouldn't be classed as a backtracking solution :]] This will
work given that there is a solution, time and the proper functioning of
random.choice. It will work better if the number of possible solutions
comes closer to n! simply because it will get more likely then that
any full drawing will be a solution too. So the more family members
and the less restrictions, the more likely it succeeds in a few tries.
OTOH, the more tries it takes the happier I am that I didn't had to go
through it in real live:)


class Hat:
    ...
    def hussle(self):
	'''hussle the hat until the drawing is valid'''
	if self.possibilities() == 0:
	    raise 'Even eternity won\'t give a valid hussle'
	self.tries = 0
	while 1:
            if self.tries > 999:
                raise 'I am bored, can\'t find a solution quick enough'
	    hat, self._drawn, self.tries = self._lots[:], [], self.tries+1
	    for drawer in self._lots:
		lot = random.choice(hat)
		if lot in self._blanks[drawer]:
		    break
		hat.remove(lot)
		self._drawn.append(lot)
	    else:
		return

    def possibilities(self):
        '''this should return the size of the anwser space,
        but now it simply returns the number of permutations of the lots'''
	U = reduce(lambda x,y: x*y, range(1, len(self._lots)+1), 1) # len!
	return U


Being mad I just wanted to know in how many ways the drawing requirements
could be fullfilled, cause this would allow a more contrieved approach.
Just immagine all solutions being ordered and given a number (e.g. the order
in which they were to be generated by a straight forward backtracking
algoritme), and a way to determine the number of solutions right to any
point in that ordered solution space. So we know the number of solutions,
and can directly 'draw' one with random.choice(range(nr-of-solutions)).
Now we will use a straightforward backtracking algoritme to generate the
solutions in the before mentioned order. *But* instead of generating all
possibilities we skip those parts of the solution tree in which the drawn
solution can't be found. This would lead us straight to the anwser:)


> I thought of another approach that might solve your problem -- to use a
> randomized algorithm which admits a relatively small but still non-zero
> probability to the assignments you'd prefer to proscribe.  Then your
> daughters could comfort themselves with the thought that they're
> unlikely to have to give/receive presents to/from each other.  For

I could live with this, but they would object fearcefully if it happened.

> instance, you could get everyone to assign a positive number to everyone
> else.  They should assign lower numbers to people they'd rather not give
> presents to (perhaps you don't have to worry too much about who they'd
> rather not receive presents from, since they're not supposed to know,
> anyway).  Say we decide to call the people in your family F={P_1, ...,
> P_n}.  Let G_0=R_0=F.  Here, G stands for givers, R for receivers.
> Construct sets G_i, R_i inductively as follows:

> Choose a person P randomly from G_{i-1}.  They've given you a function
> f:F->{positive numbers}.

> Let T=sum {f(P_l) | P_l in R_{i_1}}  Choose a person Q at random from
> R_{i-1} in such a way that the probability of a person Q' being chosen
> is given by f(Q')/T.

> Let G_i=G_{i-1}\P, R_i=R_{i-1}\Q, and let the corresponding pair be
> (P,Q).  Tell P that they're to give something to Q.

As I said, my mind is blurred, but I think this doesn't account for
me not being allowed to draw myself. This is not a matter of preference,
it's essential:)

-- 
groetjes, carel