Draft:Rao–Sandelius shuffle
Submission declined on 22 July 2024 by CFA (talk). This submission is not adequately supported by reliable sources. Reliable sources are required so that information can be verified. If you need help with referencing, please see Referencing for beginners and Citing sources.
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
| ![]() |
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.