The Fisher-Yates shuffle is backward
possiblywrong.wordpress.com
The Fisher-Yates shuffle is backward
1–10 of 23 posts
Re: The Fisher-Yates shuffle is backward
#2That’s funny. I’ve always done it the forwards way. I didn’t even realise that wasn’t the usual way.
I suppose one of the benefits of having a poor memory is that one sometimes improves things in the course of rederiving them from an imperfect recollection.
Re: The Fisher-Yates shuffle is backward
#3Huh I didn't know the backwards version was more common, it seems odd.
You could also call the last version the online version, as it will ensure the partial list is random at any point in time (and can be used for inputs with indeterminate length, or to extend a random list with new elements, sample k elements etc.)
Not too sure if the enumerate is necessary. I usually dislike using it just to have an index to play around with. A similar way of doing the same thing is:
for x in source:
a.append(x)
i = random.randint(0, len(a))
a[i], a[-1] = a[-1], a[i]
Re: The Fisher-Yates shuffle is backward
#4Huh I didn't know the backwards version was more common, it seems odd. You could also call the last version the online version, as it will ensure the partial list is random at any point in time (and can be used for inputs with indeterminate length, or to extend a random list with new elements, sample k elements etc.) Not too sure if the enumerate is necessary. I usually dislike using it just to have an index to play…
> sample k elements
Not quite sure what you have in mind here, but you need reservoir sampling for this in order to make the selection uniformly random (which I assume is what's desired)
Re: The Fisher-Yates shuffle is backward
#5I find the backward version slightly more intuitive. Here’s why:
Suppose I want to uniformly randomly shuffle a deck of cards in a single pass. I stick the deck on the table and call it the non-shuffled pile. My goal is to move the deck, one card at a time, into the shuffled pile. First I need to select a card, uniformly at random, to be the bottom card of the new pile, and I move it over. Then I select another card, uniformly at random from the still non-shuffled cards, and put it on top of the bottom shuffled card. I repeat this until I’ve moved all the cards, so that each card in the shuffled pile is a uniform random selection from all of the cards it could have been. And that’s it.
One can think of this as random selection, whereas the “forward” version is like random insertion of a not-random card into a shuffled pile. And for whatever reason I tend to think of the selection version first.
Re: The Fisher-Yates shuffle is backward
#6Huh I didn't know the backwards version was more common, it seems odd. You could also call the last version the online version, as it will ensure the partial list is random at any point in time (and can be used for inputs with indeterminate length, or to extend a random list with new elements, sample k elements etc.) Not too sure if the enumerate is necessary. I usually dislike using it just to have an index to play…
> sample k elements Not quite sure what you have in mind here, but you need reservoir sampling for this in order to make the selection uniformly random (which I assume is what's desired)
You can just use this algorithm but ignore everything after the first k elements. The algorithm still works if you don't store anything beyond the first k elements but just pretend they are there.
Re: The Fisher-Yates shuffle is backward
#7[deleted]
Re: The Fisher-Yates shuffle is backward
#8I find the backward version slightly more intuitive. Here’s why: Suppose I want to uniformly randomly shuffle a deck of cards in a single pass. I stick the deck on the table and call it the non-shuffled pile. My goal is to move the deck, one card at a time, into the shuffled pile. First I need to select a card, uniformly at random, to be the bottom card of the new pile, and I move it over. Then I select another card,…
For what it's worth, I think of the forward version as randomly selecting a card and putting it at the bottom of the new pile (0..i in the array).
Re: The Fisher-Yates shuffle is backward
#9Very interesting article!
For me, the reason for reaching for the “backwards” version first is that it wasn’t as clear to me that the “forward” version makes a uniform distribution.
Even after reading the article.
I appreciated the comment here about inserting a card at a random location, but that also isn’t quite right, because you swap cards not insert. Nevertheless, that did it for me.
Re: The Fisher-Yates shuffle is backward
#10one algo "creates" shuffled subarray and grows it - the other "chooses" random cards one at a time
both seem intuitive from individual perspectives