Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^2: A bad shuffle

by tlm (Prior)
on Mar 20, 2005 at 23:37 UTC ( #441074=note: print w/replies, xml ) Need Help??


in reply to Re: A bad shuffle
in thread A bad shuffle

Thank you for the information. Perhaps I should have made clearer in that my encounter with this algorithm, which motivated the whole write up, was in research-oriented/scientific code in which it was being used to sample permutations of an array uniformly at random. My contention is that this is a misuse of this algorithm, because it does not sample the space of permutations uniformly.

But in light of what you write about the algorithm's standing and pedigree, the title of my meditation is an awful one. Maybe the whole node should be retracted for the sake of not confusing others. Let me know what you think.


Update: I found a version of Fisher-Yates online (linked from here):

#include <stdlib.h> void shuffle(int *array, size_t n) { if (n > 1) { size_t i; for (i = 0; i < n - 1; i++) { /**/ size_t j = i + rand()/(RAND_MAX / (n - i) + 1); /**/ int t = array[j]; array[j] = array[i]; array[i] = t; } } }
This is equivalent to the algorithm used by my random_perm, not the one used by naive_shuffle. To get the latter algorithm, the lines indicated with /**/ above would have to be changed to:
for (i = 0; i < n; i++) { size_t j = rand()/(RAND_MAX / n);
the lowliest monk

Replies are listed 'Best First'.
Re^3: A bad shuffle
by Zaxo (Archbishop) on Mar 20, 2005 at 23:55 UTC

    No, don't withdraw it. I think the thing to do is try and figure out the difference between a "fair shuffle" and a uniformly distributed selection over permutations.

    Are the two the same if there are identical cards in the deck? What is the problem that motivated this?

    Sometimes confusion, like greed, is good.

    After Compline,
    Zaxo

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://441074]
help
Chatterbox?
[james28909]: what i am trying to accomplish is piping the output of ffmpeg to yet another encryption routine using libsodium. and hopefully once that is done i will be able to forward the packets to discord servers
[RonW]: choroba: Please define "high end" and "low end"
[LanX]: choroba: subversive (as usual ;)
[james28909]: i dunno, if i didnt have so little experience in linux i would swap. but it would be to much of a learning curve for me right now.
[choroba]: Low-end is defined as the Perl that generates millions of income
[choroba]: sorry, that's high-end, of coursse
[choroba]: low end, in my talk, will be code that "we don't touch because it works" and noone knows why
[choroba]: I want to present the most bizzare bugs and misfeatures I met when working for a large financial institution
[choroba]: I already gave a similar talk to my friends in a pub and at an internal conference at work and people liked it, so maybe...
[choroba]: LanX: That's the heritage, I can't do anything else

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (17)
As of 2017-05-22 21:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?