Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: A bad shuffle

by chas (Priest)
on Mar 21, 2005 at 05:08 UTC ( #441120=note: print w/replies, xml ) Need Help??


in reply to A bad shuffle

"But the real problem with this subroutine is that it does not sample the space of permutations uniformly."
It is certainly true that the method described initially does not sample the space of permutations uniformly because the permutations utilized are all a product of $n transpositions, so in particular they all have the same parity (even if $n is even, etc). Zaxo's comment that there may be some difference between a "fair shuffle" and a uniformly distributed selection over permutations" is perceptive. A shuffle might be considered "fair" if it tends to remove specific orderings that exist (e.g. in playing cards, one wants to nullify the effect of various groupings that have occurred in previous hands.) On the other hand, if one wants to model what actually occurs in a sequence of "random" shuffles, then restricting to permutations of fixed parity seems objectionable. It's a bit hard to define what "randomizing" shuffle means; Perci Diaconis (a highly respected mathematician) has studied this and written some good articles on the subject which should be found easily by web search.
chas

Replies are listed 'Best First'.
Re^2: A bad shuffle
by Anonymous Monk on Mar 21, 2005 at 10:12 UTC
    Shuffling is a classical problem in the algorithms literature. I've encountered the problem many times, and a "fair shuffle" always means that any permutation of the input list has an equal chance of being the outcome. With other words, there's no difference between "fair shuffle" and "uniformly distributed selection over permutations".

    Only you like to play word games, and start redefining well known terms.

      Well, that is a way to define "fair", but my initial comment was that *that* doesn't hold for the first method presented since each of the possible permutations has the same parity.
      (The problem of a "random" shuffle is a real one and not word play at all. Consider a dealer shuffling cards in a poker game; how should he do it to maximize the randomness of the result - should he shuffle three times, 7 times, ...? Should the shuffles be somewhat careless (so the cards son't interleave perfectly? (Yes to latter!) Here the idea is that there will be some fixed shuffling routine (e.g. shuffle, shuffle, box, shufffle), but one wants the result to be sufficiently randomized. This isn't precisely the same thing as what the OP asked, but is often what is actually desired when one discusses the question of a "fair" or "random" shuffle. This seemed to be alluded to in one of Zaxo's replies, and as I mentioned it has been analyzed in the liturature.)
      chas

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://441120]
help
Chatterbox?
[Discipulus]: marioroy did you know zentara is back to themonastery? he was used to be one of the best parallel programming monks
[makita]: sign_types parameter in XML::Compile::WSS ::Signature Does have anybody experience how to use it?
[makita]: Need to sign more elements but all types I put in array are ignored. And is always signed only the body
[Discipulus]: no makita sorry. i see in the synopsis of the module: "WARNING: Only limited real-life experience" might be better compose a SOPW with some code example and data

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (10)
As of 2017-03-23 08:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Should Pluto Get Its Planethood Back?



    Results (285 votes). Check out past polls.