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


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


;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:
* &nbsp; It modifies the input array in-place. 
* &nbsp; If that is unreasonable in your programming language, you may amend the algorithm to return the shuffled items as a new array instead.
* &nbsp; The algorithm can also be amended to iterate from left to right, if that is more convenient.


;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.)


;Related task:
* [[Sattolo cycle]]


{{Template:Strings}}
<br><br>

