Jump to content

Draft:Rao–Sandelius shuffle

From Wikipedia, the free encyclopedia

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:

  1. For each element to be shuffled, select a random digit 0 through 9.
  2. Group elements that selected the same random digit into sub-lists.
  3. Place the sub-lists in numerical order based on the digit selected.
  4. 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.

  1. For each element to be shuffled, select a random bit.
  2. Place all the elements that selected 0 ahead of all elements that selected 1.
  3. 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
  backn - 1
  outer: while true:
    b ← uniform random bit
    while b ≠ 1
      frontfront + 1
      if front > back then break outer
    b ← uniform random bit
    while b ≠ 0
      backback - 1
      if frontback then break outer
    exchange A[front] and A[back]
    frontfront + 1
    backback - 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]
  1. ^ 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.