The   [[wp:Knuth shuffle|Knuth shuffle]]   (a.k.a. the Fisher-Yates shuffle)   is an algorithm for randomly shuffling the elements of an array.

{{task heading}}

Implement the Knuth shuffle for an integer array (or, if possible, an array of any type).

{{task heading|Specification}}

Given an array '''''items''''' with indices ranging from ''0'' to '''''last''''', the algorithm can be defined as follows (pseudo-code):

 '''for''' ''i'' '''from''' ''last'' '''downto''' 1 '''do''':
     '''let''' ''j'' = random integer in range ''0'' <math>\leq</math> ''j'' <math>\leq</math> ''i''
     '''swap''' ''items''[''i''] '''with''' ''items''[''j'']

Notes:
* It modifies the input array in-place. If that is unreasonable in your programming language, you may amend the algorithm to return the shuffled items as a new array instead.
* The algorithm can also be amended to iterate from left to right, if that is more convenient.

{{task heading|Test cases}}

{| class="wikitable"
|-
! Input array
! Possible output arrays
|-
| <tt>[]</tt>
| <tt>[]</tt>
|-
| <tt>[10]</tt>
| <tt>[10]</tt>
|-
| <tt>[10, 20]</tt>
| <tt>[10, 20]</tt><br><tt>[20, 10]</tt>
|-
| <tt>[10, 20, 30]</tt>
| <tt>[10, 20, 30]</tt><br><tt>[10, 30, 20]</tt><br><tt>[20, 10, 30]</tt><br><tt>[20, 30, 10]</tt><br><tt>[30, 10, 20]</tt><br><tt>[30, 20, 10]</tt>
|}

(These are listed here just for your convenience; no need to demonstrate them on the page.)

{{task heading|Related tasks}}

* [[Sattolo cycle]]

<hr>