![]() ![]() In the first step, every number has a 1/N probability of getting into the first slot. For N > 2, you just need to show that each of 1 through N has an equal chance of getting the k-th slot for 1 through N. This is easy to verify for N = 2: You are just flipping a coin to decide if you swap 1 with 2. Starting with the ordered sequence 1, 2, 3…N, the shuffling algorithm goes like this: for k = 1 to N-1 It’s called Fisher-Yates/Knuth shuffling. Enter Fisher/Yates/Knuthīut you can actually do this with N random numbers. The above method actually generates a uniformly random permutation within a reasonable time: the standard coupon collector argument shows that you need ~N*logN random numbers. Then, pick the previously unseen unique numbers to extract a subsequence. The other day, I was modeling something in Excel (“data scientists” out there: laugh all you want, but you too might find this post interesting) and needed to generate a random permutation.Ĭasual Googling resulted in pretty disappointing information: many suggested to generate a bunch of random integers in, possibly with repeats, until you cover all N integers. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |