45 lines
1.5 KiB
Text
45 lines
1.5 KiB
Text
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>
|