The   Knuth shuffle   (a.k.a. the Fisher-Yates shuffle)   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 
  
    
      
        ≤
      
    
    {\displaystyle \leq }
  
 j 
  
    
      
        ≤
      
    
    {\displaystyle \leq }
  
 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.


Test cases



 Input array

 Possible output arrays


 []

 []


 [10]

 [10]


 [10, 20]

 [10, 20]
[20, 10]


 [10, 20, 30]

 [10, 20, 30]
[10, 30, 20]
[20, 10, 30]
[20, 30, 10]
[30, 10, 20]
[30, 20, 10]

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



Related task

 Sattolo cycle



Other tasks related to string operations:

Metrics
 Array length
 String length
 Copy a string
 Empty string  (assignment)
Counting
 Word frequency
 Letter frequency
 Jewels and stones
 I before E except after C
 Bioinformatics/base count
 Count occurrences of a substring
 Count how many vowels and consonants occur in a string
Remove/replace
 XXXX redacted
 Conjugate a Latin verb
 Remove vowels from a string
 String interpolation (included)
 Strip block comments
 Strip comments from a string
 Strip a set of characters from a string
 Strip whitespace from a string -- top and tail
 Strip control codes and extended characters from a string
Anagrams/Derangements/shuffling
 Word wheel
 ABC problem
 Sattolo cycle
 Knuth shuffle
 Ordered words
 Superpermutation minimisation
 Textonyms (using a phone text pad)
 Anagrams
 Anagrams/Deranged anagrams
 Permutations/Derangements
Find/Search/Determine
 ABC words
 Odd words
 Word ladder
 Semordnilap
 Word search
 Wordiff  (game)
 String matching
 Tea cup rim text
 Alternade words
 Changeable words
 State name puzzle
 String comparison
 Unique characters
 Unique characters in each string
 Extract file extension
 Levenshtein distance
 Palindrome detection
 Common list elements
 Longest common suffix
 Longest common prefix
 Compare a list of strings 
 Longest common substring
 Find common directory path
 Words from neighbour ones
 Change e letters to i in words
 Non-continuous subsequences
 Longest common subsequence
 Longest palindromic substrings
 Longest increasing subsequence
 Words containing "the" substring
 Sum of the digits of n is substring of n
 Determine if a string is numeric
 Determine if a string is collapsible
 Determine if a string is squeezable
 Determine if a string has all unique characters
 Determine if a string has all the same characters
 Longest substrings without repeating characters
 Find words which contains all the vowels
 Find words which contains most consonants
 Find words which contains more than 3 vowels
 Find words which first and last three letters are equals
 Find words which odd letters are consonants and even letters are vowels or vice_versa
Formatting
 Substring
 Rep-string
 Word wrap
 String case
 Align columns
 Literals/String
 Repeat a string
 Brace expansion
 Brace expansion using ranges
 Reverse a string
 Phrase reversals
 Comma quibbling
 Special characters
 String concatenation
 Substring/Top and tail
 Commatizing numbers
 Reverse words in a string
 Suffixation of decimal numbers
 Long literals, with continuations 
 Numerical and alphabetical suffixes
 Abbreviations, easy
 Abbreviations, simple
 Abbreviations, automatic
Song lyrics/poems/Mad Libs/phrases
 Mad Libs
 Magic 8-ball
 99 Bottles of Beer
 The Name Game (a song)
 The Old lady swallowed a fly
 The Twelve Days of Christmas
Tokenize
 Text between
 Tokenize a string
 Word break problem
 Tokenize a string with escaping
 Split a character string based on change of character
Sequences
 Show ASCII table
 De Bruijn sequences
 Self-referential sequences
 Generate lower case ASCII alphabet




 
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program knuthshuffle64.s   */
 
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:      .asciz "Value  : @ \n"
szCarriageReturn: .asciz "\n"
 
.align 4
TableNumber:         .quad   1,2,3,4,5,6,7,8,9,10
                     .equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConversion:         .skip 30
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                        // entry of program 
    ldr x0,qAdrTableNumber                   // address number table
    mov x1,NBELEMENTS                       // number of élements 
    bl knuthShuffle
    ldr x2,qAdrTableNumber
    mov x3,0
1:                                           // loop display table
    ldr x0,[x2,x3,lsl 3]
    ldr x1,qAdrsZoneConversion               // display value
    bl conversion10S                          // call function
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConversion 
    bl strInsertAtCharInc
    bl affichageMess                         // display message
    add x3,x3,1
    cmp x3,NBELEMENTS - 1
    ble 1b
 
    ldr x0,qAdrszCarriageReturn
    bl affichageMess   
    /*    2e shuffle             */
    ldr x0,qAdrTableNumber                   // address number table
    mov x1,NBELEMENTS                        // number of élements 
    bl knuthShuffle
    ldr x2,qAdrTableNumber
    mov x3,0
2:                                           // loop display table
    ldr x0,[x2,x3,lsl 3]
    ldr x1,qAdrsZoneConversion               // display value
    bl conversion10S                         // call function
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConversion 
    bl strInsertAtCharInc
    bl affichageMess                         // display message
    add x3,x3,1
    cmp x3,NBELEMENTS - 1
    ble 2b
 
100:                                         // standard end of the program 
    mov x0,0                                 // return code
    mov x8,EXIT                              // request to exit program
    svc 0                                    // perform the system call
 
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrTableNumber:          .quad TableNumber
qAdrsZoneConversion:      .quad sZoneConversion
/******************************************************************/
/*     Knuth Shuffle                                  */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements */
knuthShuffle:
    stp x1,lr,[sp,-16]!         // save  registers
    stp x2,x3,[sp,-16]!         // save  registers
    stp x4,x5,[sp,-16]!         // save  registers
    stp x6,x7,[sp,-16]!         // save  registers
    mov x5,x0                   // save table address
    mov x6,x1                   // save number of elements
    mov x2,0                    // start index
1:
    mov x0,0
    mov x1,x2                   // generate aleas
    bl extRandom
    ldr x3,[x5,x2,lsl 3]        // swap number on the table
    ldr x4,[x5,x0,lsl 3]
    str x4,[x5,x2,lsl 3]
    str x3,[x5,x0,lsl 3]
    add x2,x2,1                 // next number
    cmp x2,x6                   // end ?
    blt 1b                      // no -> loop
 
100:
    ldp x6,x7,[sp],16           // restaur  2 registers
    ldp x4,x5,[sp],16           // restaur  2 registers
    ldp x2,x3,[sp],16           // restaur  2 registers
    ldp x1,lr,[sp],16           // restaur  2 registers
    ret
/******************************************************************/
/*     random number                                          */ 
/******************************************************************/
/*  x0 contains inferior value */
/*  x1 contains maxi value */
/*  x0 return random number */
extRandom:
    stp x1,lr,[sp,-16]!        // save  registers
    stp x2,x8,[sp,-16]!        // save  registers
    stp x19,x20,[sp,-16]!      // save  registers
    sub sp,sp,16               // reserve 16 octets on stack
    mov x19,x0
    add x20,x1,1
    mov x0,sp                  // store result on stack
    mov x1,8                   // length 8 bytes
    mov x2,0
    mov x8,278                 //  call system Linux 64 bits Urandom
    svc 0
    mov x0,sp                  // load résult on stack
    ldr x0,[x0]
    sub x2,x20,x19             // calculation of the range of values 
    udiv x1,x0,x2              // calculation range modulo
    msub x0,x1,x2,x0
    add  x0,x0,x19             // and add inferior value
100:
    add sp,sp,16               // alignement stack 
    ldp x19,x20,[sp],16        // restaur  2 registers
    ldp x2,x8,[sp],16          // restaur  2 registers
    ldp x1,lr,[sp],16          // restaur  2 registers
    ret                        // return to address lr x30
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
 