Draft:Rao–Sandelius Shuffle
Review waiting, please be patient.
This may take 3 months or more, since drafts are reviewed in no specific order. There are 3,191 pending submissions waiting for review.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Reviewer tools
|
The Rao–Sandelius shuffle is a Divide-and-conquer algorithm for shuffling a finite sequence. The algorithm takes a list of all the elements of the sequence, and for each element draws a uniform random value from 0 to k-1. The list is broken up into k subsequences by the random value chosen, which are further shuffled.[1]
For an array with entries, the algorithm consumes random digits and performs swaps. This appears worse than the Fisher-Yates Shuffle, which consumes random digits and performs swaps. However, because of the random access pattern of the Fisher-Yates shuffle, the Rao-Sandelius Shuffle can be faster for large due to its cache friendliness.[2]
Original Method Using Random Digit Table[edit]
Rao described an algorithm for shuffling the numbers 1 through n using a table of random decimal digits. [3] Sandelius described a procedure for shuffling a deck with n cards using random decimal digits. [4] Sandelius includes the optimization that for a subdeck of length 2, you only need a single random digit. In the original, the order is kept for an odd random digit, and swapped for an even random digit. In either case the algorithm is as follows:
- For each element to be shuffled, select a random digit 0 through 9.
- Group elements that selected the same random digit into sub-lists.
- Place the sub-lists in numerical order based on the digit selected.
- Repeat on any sub-lists of size 2 or greater.
Length 2 Optimization[edit]
Sandelius included the following optimization: If the sub-list is of length 2, draw a single random digit. Swap the order if the digit is even, and leave it unchanged if the digit is odd.
Implementation with random bits[edit]
It is straightforward to adapt a version of this algorithm to a computer using k=2.
- For each element to be shuffled, select a random bit.
- Place all the elements that selected 0 ahead of all elements that selected 1.
- Repeat on the 2 sub-lists. This step can be parallelized.
The Size-2 speedup can also be applied in this case. Preserving the order if 1 is chosen, and swapping if 0 is chosen.
Here is pseudocode for an in-place version of the algorithm (for a zero-based array):
function rs_shuffle(A, n): if n < 2 then return if n = 2 then: b ← uniform random bit if b = 0 then exchange A[0] and A[1] return rs_shuffle_large(A, n)
function rs_shuffle_large(A, n): front ← 0 back ← n - 1 outer: while true: b ← uniform random bit while b ≠ 1 front ← front + 1 if front > back then break outer b ← uniform random bit while b ≠ 0 back ← back - 1 if front ≥ back then break outer exchange A[front] and A[back] front ← front + 1 back ← back - 1 if front > back then break outer rs_shuffle(A, front) rs_shuffle(A + front, n - front)
Each algorithm pass is effectively an Inverse-GSR 2-shuffle.
References[edit]
- ^ Bacher, Axel; Bodini, Olivier; Hwang, Hsien-Kuei; Tsai, Tsung-Hsi (February 2017). "Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation". ACM Transactions on Algorithms. 13 (2): 24:4. doi:10.1145/3009909. Retrieved 12 May 2024.
- ^ Mitchell, Rory; Stokes, Daniel; Frank, Eibe; Holmes, Geoffrey (February 2022). "Bandwidth-Optimal Random Shuffling for GPUs". ACM Transactions on Parallel Computing. 9 (1): 17. arXiv:2106.06161. doi:10.1145/3505287.
- ^ Rao, C. Radhakrishna (August 1961). "Generation of random permutations of given number of elements using random sampling numbers" (PDF). The Indian Journal of Statistics. 23 (3): 305–307. Retrieved 12 May 2024.
- ^ Sandelius, Martin (July 1962). "A Simple Randomization Procedure". Journal of the Royal Statistical Society. 24 (2): 472–481. doi:10.1111/j.2517-6161.1962.tb00474.x.