automatic "lotjes trekken"
cfelling at iae.nl
Sun Nov 28 23:10:15 CET 1999
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
> 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.
More information about the Python-list