# Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?

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?

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.

• 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. – Alireza Sep 3 '19 at 18:56
• @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. – Peter Taylor Sep 3 '19 at 21:28
• Ahh, I see. That's right. They are the same. – Alireza Sep 4 '19 at 5:03

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.