3
$\begingroup$

I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it.

Python starts from the end of the array to the start. Looking at the algorithm I didn't see any benefits in doing so compared to starting with the start and going to the end.

I was wondering, considering that looping backwards adds a thin layer of complexity, are there any benefits in doing so?

$\endgroup$

2 Answers 2

1
$\begingroup$

With 0-indexed arrays, and stopping the loop at the last non-trivial random selection, we have

for x = n to 2 step -1:
    swap A[x-1], A[uniform_random(0 inclusive to x exclusive)]

vs

for x = 0 to n-2 step 1:
    swap A[x], A[uniform_random(x inclusive to n exclusive)]

which would probably be implemented as

for x = 0 to n-2 step 1:
    swap A[x], A[x + uniform_random(0 inclusive to n-x exclusive)]

So the forward loop has at least as much complexity.

I would claim that the simplest version is looping backwards in a 1-indexed environment (i.e. 1-indexed arrays and random number generation):

for x = n to 2 step -1:
    swap A[x], A[uniform_random(1 inclusive to x inclusive)]

There are various other variants possible: e.g. in the first example, we could loop x = n-1 to 1 step -1; in the second example, we could use two loop variables instead of one; etc.

$\endgroup$
3
  • $\begingroup$ thank you for your response. swap A[x], A[x + uniform_random(0 inclusive to n-x exclusive)] doesn't seem right to me. The lower bound is x and the upper bound is the last element of the array which is n-1. $\endgroup$
    – user1984
    Sep 3, 2019 at 18:56
  • $\begingroup$ @Alireza, that's right. An inclusive upper bound of n-1 corresponds to an exclusive upper bound of n, as in the second code block. Then pull out the x + and you get an exclusive upper bound of n-x. $\endgroup$ Sep 3, 2019 at 21:28
  • $\begingroup$ Ahh, I see. That's right. They are the same. $\endgroup$
    – user1984
    Sep 4, 2019 at 5:03
0
$\begingroup$

The Wikipedia link you shared also provides an implementation that works starting from the end of the list (followed by an implementation starting from the beginning).

From wikipedia -- To shuffle an array a of n elements (indices 0..n-1): for i from n−1 downto 1 do j ← random integer such that 0 ≤ j ≤ i exchange a[j] and a[i]

An equivalent version which shuffles the array in the opposite direction (from lowest index to highest) is:

-- To shuffle an array a of n elements (indices 0..n-1): for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j] 

Functionally, both are equivalent. Some may argue that the versions have different cache/prefetcher performance and instruction-level optimizations but I don't think that influenced the decision.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.