automatic "lotjes trekken"

[Carel Fellinger]

Tim Peters <tim_one at email.msn.com> wrote:

> Here's an example showing why you should *not* take the other approaches
> that have been suggested:
...example and explanation snipped...

aiaiaia, mio stupido he. glad my kids aren't lurking on this newsgroup yet;
otherwise they would have argued for a redraw. Anyhow, now I'm forced to
redo the programming. Thanks for sharing all the insights!


> Here are three approaches that work:

> 1) A variant of the one you're already using:  generate a *permutation* at
> random, in one gulp.  Then check whether it meets the restrictions.  If it
> doesn't, try again.  Then each solution clearly has an equal chance of
> getting picked.

> Deep flaw #1:  As explained here a few months ago, Python's random-number
> generator isn't capable of generating more than about 1E12 distinct
> permutations, so even for a list of size 20 it's incapable of generating
> "almost all" of the possible permutations.

I was aware of this one, thanks to the list being a fine tutor.

> Deep flaw #2:  As with your current approach, it will run "forever" if there

the solution as i posted bailed out after 1000 tries, not exactly forever:)

> is no solution.  A variant of the birthday paradox kicks in here too:  even
> if all permutations could be generated at random, "at random" means you get
> duplicates.  The expected number of permutations you have to generate at
> random before you see each of the N! possibilites at least once is about N!
> * ln(N!) (ln == log to the base e).  Cut off the search earlier than that,
> and chances are better than half that you never saw at least one permutation
> (which may have been a solution).

But I have to rethink this one. I'm not trying to generate all solutions,
just one. So in what way would this make the algoritme unfair? Each time
I call this program is an event on its own, unrelated to the previous. So
the 'missing' solution might well be a different one in each run.


> 2) The approach below:  generate all possible solutions, then simply apply
> random.choice to the list of results.  For your size of problem, it will run
> quickly, and in any case runs faster the more restrictions there are.

A variation of this would be to number the solutions, draw a number and
generate that solution as I proposed in a previous post. I will use your
info and some rainy days to figure out whether it is feasable at all.
Would circumvent the next deepflaw too.

> Deep flaw:  For larger problems, it's utterly impractical (too many
> solutions).

> 3) Go back to the theory:  at each step, analyze the board according to the
> method sketched yesterday, and put a rook on that step's distinguised square
> with probability given by the number of solutions that have a rook on that
> square divided by the total number of solutions (i.e., with or without a
> rook on that square).  In the example above, this means that if your first
> choice is wrt the Carel->Martijn square, you would first compute that there
> are 2 solutions with a rook there and 1 without, and so you should put the
> rook there with probability 2/3.  That's the way to do this properly without
> backtracking -- and if you think it's worth the effort, your winter is far
> too long <wink -- but it is a difficult programming problem!>.

still opting for my own variation of 2, but if that fails, I'll try 3.


-- 
groetjes, carel