Figure 1 An example of Fisher–Yates shuffle. 3 permutations. But as you may know, there are only 3 x 2 x 1 = 6 possible ways to mix up the order of those three cards: 123, 132, 213, 231, 312, 321. If you list all possible permutations resulting from the naïve method, you will find that the combinations 132, 213 and 231 come up five times, while 123, 312 and 321 come up only four times. Obviously, the result is biased. If you think intuitively, since 27 is not divisible by 6 (and nn or n > 2 is not divisible by n! in general), some of the possible permutations must happen more often than others (if all of them are equally likely to occur, the number of shuffles will be a multiple of 6). The chances are not equal, so the naïve method is not random. This is similar to the usual way to shuffle cards: In simple terms, we take an entire bunch of cards and swap it with another bunch of cards in the sequence. But these methods do not result in a random outcome, because the shuffled cards continue to circulate within the system. Contrast this with Fisher–Yates. Since a card is removed from consideration after each shuffle (and gets put into a new deck), the pool to be shuffled at each stage gets smaller, and for our three-card deck there wi l l be 3 x 2 x 1 = 6 permutations after three shuffles. Note that these permutations are calculated the same way as the possible ways of mixing up three cards: they both use the factorial function n! = n x (n - 1) … x 3 x 2 x 1, or 3! = 3 x 2 x 1 in this case which is equivalent to 3P3. They are essential ly the same algorithm in the sense that they are counted the exact same way. So the randomness behind the original selections of n is preserved throughout the permutations, and this is why we can guarantee Fisher– Yates is a fully random sequence provided n is chosen randomly. Creating a Less Random Playlist That Feels More “Random” Now let’s return to our random sequence 3-9-6-25-10-4-1-8-7 in Figure 1. We can call it a shuffled playlist of ten songs and say that songs 1, 4, 7, and 10 are by Adele (artist A), songs 2, 5, and 8 are by BTS (artist B), and songs 3, 6, and 9 are by Celine Dion (artist C). It looks like this: Celine Dion > Celine Dion > Celine Dion > BTS > BTS > Adele > Adele > Adele > BTS > Adele Which doesn’t look random at all! That’s because we focus on the unusual patterns of three Celine Dion and three Adele songs in a row. If you were like Spotify users between 2012 and 2014, you’d have rushed to complain [5] about all the times the shuffle algorithm played non-K-pop music over and over (assuming you also listened to K-pop before 2014). There were so many complaints, in fact, that Spotify retired the Fisher– Yates algorithm – yes, they originally used Fisher–Yates to shuffle playlists [6] – and introduced a new shuffling algorithm. Now, when you shuffle a playlist, different songs by the same artist and in the same genre are distributed roughly evenly across the list [7]. The Spotify engineers made the shuffle less random to convince you that it became more random. n Existing sequence New sequence 3 1 2 3 4 5 6 7 8 9 10 3 8 1 2 4 5 6 7 8 9 10 3 9 5 1 2 4 5 6 7 8 10 3 9 6 2 1 2 4 5 7 8 10 3 9 6 2 3 1 4 5 7 8 10 3 9 6 2 5 5 1 4 7 8 10 3 9 6 2 5 10 2 1 4 7 8 3 9 6 2 5 10 4 1 1 7 8 3 9 6 2 5 10 4 1 2 7 8 3 9 6 2 5 10 4 1 8 1 7 3 9 6 2 5 10 4 1 8 7
RkJQdWJsaXNoZXIy NDk5Njg=