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]
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:
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.
It is straightforward to adapt a version of this algorithm to a computer using k=2.
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 Afront] and Aback] 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.
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]
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:
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.
It is straightforward to adapt a version of this algorithm to a computer using k=2.
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 Afront] and Aback] 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.