Knuth shuffle
You are encouraged to solve this task according to the task description, using any language you may know.
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 j 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
- Metrics
- 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
11l
<lang 11l>F knuth_shuffle(&x)
L(i) (x.len - 1 .< 0).step(-1)
V j = random:(0..i)
swap(&x[i], &x[j])
V x = Array(0..9) knuth_shuffle(&x) print(‘shuffled: ’x)</lang>
- Output:
shuffled: [0, 5, 7, 1, 3, 8, 4, 6, 9, 2]
360 Assembly
<lang 360asm>
- Knuth shuffle 02/11/2015
KNUTHSH CSECT
USING KNUTHSH,R15
LA R6,1 i=1
LOOPI1 C R6,=A(CARDS) do i=1 to cards
BH ELOOPI1
STC R6,PACK(R6) pack(i)=i
LA R6,1(R6) i=i+1
B LOOPI1
ELOOPI1 LA R7,CARDS n=cards LOOPN C R7,=F'2' do n=cards to 2 by -1
BL ELOOPN
L R5,RANDSEED r5=seed
M R4,=F'397204094' r4r5=seed*const
D R4,=X'7FFFFFFF' r5=r5 div (2^31-1)
ST R4,RANDSEED r4=r5 mod (2^31-1); seed=r4
LR R5,R4 r5=seed
LA R4,0 r4=0
DR R4,R7 r5=seed div n; r4=seed mod n
LA R9,1(R4) r2=randint(n)+1 [1:n]
LA R4,PACK(R7) @pack(n)
LA R5,PACK(R9) @pack(nw)
MVC TMP,0(R4) tmp=pack(n)
MVC 0(1,R4),0(R5) pack(n)=pack(nw)
MVC 0(1,R5),TMP pack(nw)=tmp
BCTR R7,0 n=n-1
B LOOPN
ELOOPN LA R6,1 i=1
LA R8,PG pgi=@pg
LOOPI2 C R6,=A(CARDS) do i=1 to cards
BH ELOOPI2
XR R2,R2 r2=0
IC R2,PACK(R6) pack(i)
XDECO R2,XD edit pack(i)
MVC 0(3,R8),XD+9 output pack(i)
LA R8,3(R8) pgi=pgi+3
LA R6,1(R6) i=i+1
B LOOPI2
ELOOPI2 XPRNT PG,80 print buffer
XR R15,R15 set return code
BR R14 return to caller
CARDS EQU 20 number of cards PACK DS (CARDS+1)C pack of cards TMP DS C temp for swap PG DC CL80' ' buffer XD DS CL12 to decimal RANDSEED DC F'16807' running seed
YREGS
END KNUTHSH
</lang>
- Output:
13 16 10 18 19 14 6 17 2 5 1 15 7 11 12 9 8 20 4 3
6502 Assembly
When the array address is known before runtime
Runs on easy6502, which has a random number generated memory-mapped at zero page address $FE that updates after every instruction. Works on any array size up to and including 256 bytes. (The code I wrote here prior to this edit was much faster but only worked on arrays of exactly 256 bytes in size). The reason for this was that constraining a random number generator that can produce any 8-bit value to a subset is tricky, since just "rolling again" if out of range will eventually cause the program to lock up if it can't produce a value in range purely by chance. This method uses a bit mask that shifts right as the loop counter decreases to zero, which means that even when only a few bytes still need to be shuffled, the routine is just as quick as it was at the beginning.
<lang 6502asm>define sysRandom $fe define tempMask $ff define range $00 define tempX $01 define tempY $02 define tempRandIndex $03 define temp $04 CreateIdentityTable:
txa sta $0200,x sta $1000,x inx bne CreateIdentityTable
- creates a sorted array from 0-255 starting at addr $1000
- also creates another one at $0200 for our test input
lda #1 sta range
ConstrainRNG: ldx #255
- max range of RNG
lda range bne outerloop jmp end
outerloop: cpx range bcc continue ;if X >= range, we need to lower X pha
txa sta tempX
lsr cmp range bcc continue2
tax
pla jmp outerloop
continue2: pla ldx tempX
continue: ldy range
KnuthShuffle: lda sysRandom and $1000,x ;and with range constrictor tay
lda $0200,y sty tempRandIndex sta temp ldy range lda $0200,y pha
lda temp sta $0200,y
pla ldy tempRandIndex sta $0200,y dec range jmp ConstrainRNG
end: brk</lang>
AArch64 Assembly
<lang AArch64 Assembly> /* 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" </lang>
ACL2
<lang Lisp>:set-state-ok t
(defun array-swap (name array i j)
(let ((ai (aref1 name array i))
(aj (aref1 name array j)))
(aset1 name
(aset1 name array j ai)
i aj)))
(defun shuffle-r (name array m state)
(if (zp m)
(mv array state)
(mv-let (i state)
(random$ m state)
(shuffle-r name
(array-swap name array i m)
(1- m)
state))))
(defun shuffle (name array state)
(shuffle-r name
array
(1- (first (dimensions name array)))
state))</lang>
Action!
<lang Action!>PROC PrintTable(INT ARRAY tab BYTE size)
BYTE i
FOR i=0 TO size-1
DO
PrintF("%I ",tab(i))
OD
PutE()
RETURN
PROC KnuthShuffle(INT ARRAY tab BYTE size)
BYTE i,j INT tmp
i=size-1 WHILE i>0 DO j=Rand(i+1) tmp=tab(i) tab(i)=tab(j) tab(j)=tmp i==-1 OD
RETURN
PROC Main()
BYTE i,size=[20] INT ARRAY tab(size)
FOR i=0 TO size-1 DO tab(i)=-50+10*i OD
PrintE("Original data:")
PrintTable(tab,size)
PutE()
KnuthShuffle(tab,size)
PrintE("Shuffled data:")
PrintTable(tab,size)
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
Original data: -50 -40 -30 -20 -10 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 Shuffled data: 0 60 70 90 80 120 10 50 30 -30 -20 110 -50 140 100 -10 -40 40 20 130
Ada
This implementation is a generic shuffle routine, able to shuffle an array of any type. <lang Ada>generic
type Element_Type is private; type Array_Type is array (Positive range <>) of Element_Type;
procedure Generic_Shuffle (List : in out Array_Type);</lang> <lang Ada>with Ada.Numerics.Discrete_Random;
procedure Generic_Shuffle (List : in out Array_Type) is
package Discrete_Random is new Ada.Numerics.Discrete_Random(Result_Subtype => Integer); use Discrete_Random; K : Integer; G : Generator; T : Element_Type;
begin
Reset (G);
for I in reverse List'Range loop
K := (Random(G) mod I) + 1;
T := List(I);
List(I) := List(K);
List(K) := T;
end loop;
end Generic_Shuffle;</lang> An example using Generic_Shuffle. <lang Ada>with Ada.Text_IO; with Generic_Shuffle;
procedure Test_Shuffle is
type Integer_Array is array (Positive range <>) of Integer;
Integer_List : Integer_Array
:= (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18);
procedure Integer_Shuffle is new Generic_Shuffle(Element_Type => Integer,
Array_Type => Integer_Array);
begin
for I in Integer_List'Range loop
Ada.Text_IO.Put(Integer'Image(Integer_List(I)));
end loop;
Integer_Shuffle(List => Integer_List);
Ada.Text_IO.New_Line;
for I in Integer_List'Range loop
Ada.Text_IO.Put(Integer'Image(Integer_List(I)));
end loop;
end Test_Shuffle;</lang>
Aime
The shuffle function works on any type (the lists are heterogenous). <lang aime>void shuffle(list l) {
integer i;
i = ~l;
if (i) {
i -= 1;
while (i) {
l.spin(i, drand(i));
i -= 1;
}
}
}</lang>
ALGOL 68
<lang algol68>PROC between = (INT a, b)INT : (
ENTIER (random * ABS (b-a+1) + (a<b|a|b))
);
PROC knuth shuffle = (REF[]INT a)VOID: (
FOR i FROM LWB a TO UPB a DO INT j = between(LWB a, UPB a); INT t = a[i]; a[i] := a[j]; a[j] := t OD
);</lang> <lang algol68>main:(
[20]INT a; FOR i FROM 1 TO 20 DO a[i] := i OD; knuth shuffle(a); print(a)
)</lang>
AppleScript
Iteration
<lang AppleScript>set n to 25
set array to {} repeat with i from 1 to n set end of array to i end repeat copy {array, array} to {unshuffled, shuffled} repeat with i from n to 1 by -1 set j to (((random number) * (i - 1)) as integer) + 1 set shuffled's item i to array's item j if j ≠ i's contents then set array's item j to array's item i end repeat
return {unshuffled, shuffled}</lang> Example: <lang AppleScript>{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25}, {14, 25, 3, 1, 12, 18, 11, 20, 16, 15, 21, 5, 22, 19, 2, 24, 8, 10, 13, 6, 17, 23, 9, 7, 4}}</lang>
Better: <lang applescript>-- Fisher-Yates (aka Durstenfeld, aka Knuth) shuffle. on shuffle(theList, l, r)
set listLength to (count theList)
if (listLength < 2) then return array
if (l < 0) then set l to listLength + l + 1
if (r < 0) then set r to listLength + r + 1
if (l > r) then set {l, r} to {r, l}
script o
property lst : theList
end script
repeat with i from l to (r - 1)
set j to (random number from i to r)
set v to o's lst's item i
set o's lst's item i to o's lst's item j
set o's lst's item j to v
end repeat
return theList
end shuffle
local array set array to {"Alpha", "Bravo", "Charlie", "Delta", "Echo", "Foxtrot", "Golf", "Hotel", "India", "Juliett", "Kilo", "Lima", "Mike"} -- Shuffle all items (1 thru -1). shuffle(array, 1, -1)</lang>
- Output:
eg. <lang applescript>{"Golf", "Foxtrot", "Echo", "Delta", "Kilo", "Charlie", "Mike", "Alpha", "Lima", "Juliett", "India", "Bravo", "Hotel"}</lang>
When a large number of random indices is required, it can actually be faster to create a list of integers and select from these using AppleScript's 'some' specifier than to call the StandardAdditions' 'random number' function repeatedly. But a better solution since Mac OS X 10.11 is to use the system's GameplayKit framework: <lang applescript>use AppleScript version "2.5" -- OS X 10.11 (El Capitan) or later use framework "Foundation" use framework "GameplayKit"
on shuffle(theList, l, r)
set listLength to (count theList)
if (listLength < 2) then return theList
if (l < 0) then set l to listLength + l + 1
if (r < 0) then set r to listLength + r + 1
if (l > r) then set {l, r} to {r, l}
script o
property lst : theList
end script
set rndGenerator to current application's class "GKRandomDistribution"'s distributionWithLowestValue:(l) highestValue:(r)
repeat with i from r to (l + 1) by -1
set j to (rndGenerator's nextIntWithUpperBound:(i))
set v to o's lst's item i
set o's lst's item i to o's lst's item j
set o's lst's item j to v
end repeat
return theList
end shuffle</lang>
Functional composition
<lang AppleScript>-- KNUTH SHUFFLE -------------------------------------------------------------
-- knuthShuffle :: [a] -> [a] on knuthShuffle(xs)
-- randomSwap :: [Int] -> Int -> [Int]
script randomSwap
on |λ|(a, i)
if i > 1 then
set iRand to random number from 1 to i
tell a
set tmp to item iRand
set item iRand to item i
set item i to tmp
it
end tell
else
a
end if
end |λ|
end script
foldr(randomSwap, xs, enumFromTo(1, length of xs))
end knuthShuffle
-- TEST ----------------------------------------------------------------------
on run
knuthShuffle(["alpha", "beta", "gamma", "delta", "epsilon", ¬
"zeta", "eta", "theta", "iota", "kappa", "lambda", "mu"])
end run
-- GENERIC FUNCTIONS ---------------------------------------------------------
-- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m, n)
if m > n then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
-- foldr :: (a -> b -> a) -> a -> [b] -> a on foldr(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from lng to 1 by -1
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldr
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn</lang>
- Output:
e.g. <lang AppleScript>{"mu", "theta", "alpha", "delta", "zeta", "gamma", "iota", "kappa", "lambda", "epsilon", "beta", "eta"}</lang>
ARM Assembly
<lang ARM Assembly>
/* ARM assembly Raspberry PI */ /* program knuthShuffle.s */
/************************************/ /* Constantes */ /************************************/ .equ STDOUT, 1 @ Linux output console .equ EXIT, 1 @ Linux syscall .equ WRITE, 4 @ Linux syscall /*********************************/ /* Initialized data */ /*********************************/ .data sMessResult: .ascii "Value : " sMessValeur: .fill 11, 1, ' ' @ size => 11 szCarriageReturn: .asciz "\n"
.align 4 iGraine: .int 123456 .equ NBELEMENTS, 10 TableNumber: .int 1,2,3,4,5,6,7,8,9,10
/*********************************/ /* UnInitialized data */ /*********************************/ .bss /*********************************/ /* code section */ /*********************************/ .text .global main main: @ entry of program
ldr r0,iAdrTableNumber @ address number table mov r1,#NBELEMENTS @ number of élements bl knuthShuffle ldr r2,iAdrTableNumber mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2] ldr r1,iAdrsMessValeur @ display value bl conversion10 @ call function ldr r0,iAdrsMessResult bl affichageMess @ display message add r3,#1 cmp r3,#NBELEMENTS - 1 ble 1b
ldr r0,iAdrszCarriageReturn bl affichageMess /* 2e shuffle */ ldr r0,iAdrTableNumber @ address number table mov r1,#NBELEMENTS @ number of élements bl knuthShuffle ldr r2,iAdrTableNumber mov r3,#0
2: @ loop display table
ldr r0,[r2,r3,lsl #2] ldr r1,iAdrsMessValeur @ display value bl conversion10 @ call function ldr r0,iAdrsMessResult bl affichageMess @ display message add r3,#1 cmp r3,#NBELEMENTS - 1 ble 2b
100: @ standard end of the program
mov r0, #0 @ return code mov r7, #EXIT @ request to exit program svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur iAdrszCarriageReturn: .int szCarriageReturn iAdrsMessResult: .int sMessResult iAdrTableNumber: .int TableNumber
/******************************************************************/ /* Knuth Shuffle */ /******************************************************************/ /* r0 contains the address of table */ /* r1 contains the number of elements */ knuthShuffle:
push {r2-r5,lr} @ save registers
mov r5,r0 @ save table address
mov r2,#0 @ start index
1:
mov r0,r2 @ generate aleas bl genereraleas ldr r3,[r5,r2,lsl #2] @ swap number on the table ldr r4,[r5,r0,lsl #2] str r4,[r5,r2,lsl #2] str r3,[r5,r0,lsl #2] add r2,#1 @ next number cmp r2,r1 @ end ? blt 1b @ no -> loop
100:
pop {r2-r5,lr}
bx lr @ return
/******************************************************************/ /* display text with size calculation */ /******************************************************************/ /* r0 contains the address of the message */ affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/ /* Converting a register to a decimal unsigned */ /******************************************************************/ /* r0 contains value and r1 address area */ /* r0 return size of result (no zero final in area) */ /* area size => 11 bytes */ .equ LGZONECAL, 10 conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area add r4,#1 @ next position cmp r4,#LGZONECAL ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/ /* division par 10 unsigned */ /***************************************************/ /* r0 dividende */ /* r0 quotient */ /* r1 remainder */ divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD /***************************************************/ /* Generation random number */ /***************************************************/ /* r0 contains limit */ genereraleas:
push {r1-r4,lr} @ save registers
ldr r4,iAdriGraine
ldr r2,[r4]
ldr r3,iNbDep1
mul r2,r3,r2
ldr r3,iNbDep1
add r2,r2,r3
str r2,[r4] @ maj de la graine pour l appel suivant
cmp r0,#0
beq 100f
mov r1,r0 @ divisor
mov r0,r2 @ dividende
bl division
mov r0,r3 @ résult = remainder
100: @ end function
pop {r1-r4,lr} @ restaur registers
bx lr @ return
/*****************************************************/ iAdriGraine: .int iGraine iNbDep1: .int 0x343FD iNbDep2: .int 0x269EC3 /***************************************************/ /* integer division unsigned */ /***************************************************/ division:
/* r0 contains dividend */
/* r1 contains divisor */
/* r2 returns quotient */
/* r3 returns remainder */
push {r4, lr}
mov r2, #0 @ init quotient
mov r3, #0 @ init remainder
mov r4, #32 @ init counter bits
b 2f
1: @ loop
movs r0, r0, LSL #1 @ r0 <- r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1) adc r3, r3, r3 @ r3 <- r3 + r3 + C. This is equivalent to r3 ? (r3 << 1) + C cmp r3, r1 @ compute r3 - r1 and update cpsr subhs r3, r3, r1 @ if r3 >= r1 (C=1) then r3 <- r3 - r1 adc r2, r2, r2 @ r2 <- r2 + r2 + C. This is equivalent to r2 <- (r2 << 1) + C
2:
subs r4, r4, #1 @ r4 <- r4 - 1
bpl 1b @ if r4 >= 0 (N=0) then loop
pop {r4, lr}
bx lr
</lang>
Arturo
<lang rebol>knuth: function [arr][ if 0=size arr -> return []
loop ((size arr)-1)..0 'i [ j: random 0 i
tmp: arr\[i] set arr i arr\[j] set arr j tmp ]
return arr
]
print knuth [] print knuth [10] print knuth [10 20] print knuth [10 20 30]</lang>
AutoHotkey
ahk forum: discussion <lang AutoHotkey>MsgBox % shuffle("1,2,3,4,5,6,7,8,9") MsgBox % shuffle("1,2,3,4,5,6,7,8,9")
shuffle(list) { ; shuffle comma separated list, converted to array
StringSplit a, list, `, ; make array (length = a0)
Loop % a0-1 {
Random i, A_Index, a0 ; swap item 1,2... with a random item to the right of it
t := a%i%, a%i% := a%A_Index%, a%A_Index% := t
}
Loop % a0 ; construct string from sorted array
s .= "," . a%A_Index%
Return SubStr(s,2) ; drop leading comma
}</lang>
For Arrays:
(translated from) <lang AutoHotkey>toShuffle:=[1,2,3,4,5,6] shuffled:=shuffle(toShuffle)
- p(toShuffle) ;because it modifies the original array
- or
- p(shuffled)
shuffle(a) {
i := a.Length()
loop % i-1 {
Random, j,1,% i
x := a[i]
a[i] := a[j]
a[j] := x
i--
}
return a
}</lang>
AutoIt
<lang AutoIt> Dim $a[10] ConsoleWrite('array before permutation:' & @CRLF) For $i = 0 To 9 $a[$i] = Random(20,100,1) ConsoleWrite($a[$i] & ' ') Next ConsoleWrite(@CRLF)
_Permute($a) ConsoleWrite('array after permutation:' & @CRLF) For $i = 0 To UBound($a) -1 ConsoleWrite($a[$i] & ' ') Next ConsoleWrite(@CRLF)
Func _Permute(ByRef $array)
Local $random, $tmp
For $i = UBound($array) -1 To 0 Step -1
$random = Random(0,$i,1)
$tmp = $array[$random]
$array[$random] = $array[$i]
$array[$i] = $tmp
Next
EndFunc
</lang>
- Output:
array before permutation: 43 57 37 20 97 98 69 76 97 70 array after permutation: 57 69 97 70 37 97 20 76 43 98
AWK
Many arrays in AWK have the first index at 1. This example shows how to shuffle such arrays. The elements can be integers, floating-point numbers, or strings. <lang awk># Shuffle an _array_ with indexes from 1 to _len_. function shuffle(array, len, i, j, t) { for (i = len; i > 1; i--) { # j = random integer from 1 to i j = int(i * rand()) + 1
# swap array[i], array[j] t = array[i] array[i] = array[j] array[j] = t } }
- Test program.
BEGIN { len = split("11 22 33 44 55 66 77 88 99 110", array) shuffle(array, len)
for (i = 1; i < len; i++) printf "%s ", array[i] printf "%s\n", array[len] }</lang>
BASIC
<lang qbasic>RANDOMIZE TIMER
DIM cards(51) AS INTEGER DIM L0 AS LONG, card AS LONG
PRINT "before:" FOR L0 = 0 TO 51
cards(L0) = L0 PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT
FOR L0 = 51 TO 0 STEP -1
card = INT(RND * (L0 + 1)) IF card <> L0 THEN SWAP cards(card), cards(L0)
NEXT
PRINT : PRINT "after:" FOR L0 = 0 TO 51
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT PRINT</lang>
- Output:
before: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 after: 27 14 37 35 3 44 25 38 46 1 22 49 2 51 16 32 20 30 4 33 36 6 31 21 41 34 9 13 0 50 47 48 40 39 7 18 19 26 24 10 29 5 12 28 11 17 43 45 8 23 42 15
Applesoft BASIC
As mentioned in the Sinclair ZX81 BASIC solution, for very small positive integer values, a string is a much more memory-efficient array, but here is an example of an array with numbers. Line 150 initializes and prints each element in the array. Line 190 performs the swap of the elements.
<lang basic> 100 :
110 REM KNUTH SHUFFLE 120 : 130 DIM A(25) 140 FOR I = 1 TO 25 150 A(I) = I: PRINT A(I);" ";: NEXT I 160 PRINT : PRINT 170 FOR I = 25 TO 2 STEP - 1 180 J = INT ( RND (1) * I + 1) 190 T = A(I):A(I) = A(J):A(J) = T: NEXT I 200 FOR I = 1 TO 25 210 PRINT A(I);" ";: NEXT I 220 END
</lang>
- Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 7 18 19 20 21 22 23 24 25
When it has finished, the screen will show (for example):
20 5 6 9 15 23 22 8 4 24 7 11 16 21 2 17 14 10 19 13 12 18 1 3 25
Sinclair ZX81 BASIC
For very small positive integer values, a string (which can be treated as an array of bytes) is much more memory-efficient than an array of numbers. In this program we shuffle a string consisting of the letters 'A' to 'Z'. The ZX81 is slow enough that we can watch the shuffle happening in real time, with items switching to inverse video display as they are shuffled. (This can be done, in the ZX81 character set, by setting the high bit in the character code.) Line 10 seeds the pseudo-random number generator. Note that strings (and arrays) are indexed from 1.
The program works with the unexpanded (1k RAM) ZX81. <lang basic> 10 RAND
20 LET A$="" 30 FOR I=1 TO 26 40 LET A$=A$+CHR$ (37+I) 50 NEXT I 60 PRINT A$ 70 FOR I=26 TO 2 STEP -1 80 LET J=1+INT (RND*I) 90 LET T$=A$(I)
100 LET A$(I)=A$(J) 110 LET A$(J)=T$ 120 PRINT AT 0,I-1;CHR$ (CODE A$(I)+128) 130 PRINT AT 0,J-1;CHR$ (CODE A$(J)+128) 140 NEXT I</lang>
- Output:
While the program is running, we will see something like this (using lower case as a stand-in for inverse video):
ABCuEFGzwJKLMNOPxySvdtiqrh
When it has finished, the screen will show (for example):
lcjbpxekzsaygumwnovfdtiqrh
BBC BASIC
<lang bbcbasic> cards% = 52
DIM pack%(cards%)
FOR I% = 1 TO cards%
pack%(I%) = I%
NEXT I%
FOR N% = cards% TO 2 STEP -1
SWAP pack%(N%),pack%(RND(N%))
NEXT N%
FOR I% = 1 TO cards%
PRINT pack%(I%);
NEXT I%
PRINT</lang>
IS-BASIC
<lang IS-BASIC>100 PROGRAM "Shuffle.bas" 110 RANDOMIZE 120 NUMERIC ARRAY(1 TO 20) 130 CALL INIT(ARRAY) 140 CALL WRITE(ARRAY) 150 CALL SHUFFLE(ARRAY) 160 CALL WRITE(ARRAY) 170 DEF INIT(REF A) 180 FOR I=LBOUND(A) TO UBOUND(A) 190 LET A(I)=I 200 NEXT 210 END DEF 220 DEF WRITE(REF A) 230 FOR I=LBOUND(A) TO UBOUND(A) 240 PRINT A(I); 250 NEXT 260 PRINT 270 END DEF 280 DEF SHUFFLE(REF A) 290 FOR I=UBOUND(A) TO LBOUND(A) STEP-1 300 LET CARD=RND(UBOUND(A)-LBOUND(A))+LBOUND(A)+1 310 IF CARD<>I THEN LET T=A(CARD):LET A(CARD)=A(I):LET A(I)=T 320 NEXT 330 END DEF</lang>
QB64
<lang QB64> shuffle and make sure that number does not take its place and between cells at least 10% ... Shuffle from Russia
a = 100: DIM d(a): x=0: k=0: t$=CHR$(9): RANDOMIZE TIMER 'Shuffle_RUS.bas PRINT ,: FOR i = 1 TO a: d(i)=i: NEXT FOR i = 1 TO 5: PRINT d(i);: NEXT: PRINT , FOR i = a-3 TO a: PRINT d(i);: NEXT: z = TIMER OPEN "b:/control.txt" FOR OUTPUT AS #1 ' ram disk WHILE x < 1
v = 0: FOR i = 1 TO a
1 m = INT(RND*a)+1: IF ABS(d(i)-d(m)) < .1*a THEN v = v+1: GOTO 1
PRINT #1, ABS(d(i)-d(m)); t$; d(i); t$; d(m); t$; i; t$; m; t$; d(i)/d(m); t$; d(m)/d(i) ' ram disk
t = d(i): d(i) = d(m): d(m) = t
NEXT
s = 0: FOR i = 1 TO a
IF d(i) = i THEN s = s+1 ' : goto 5
NEXT
5 k = k+1: PRINT: PRINT s; v,: IF s=0 THEN x = x+1
FOR i = 1 TO 5
IF d(i) = i THEN PRINT -d(i); ELSE PRINT d(i);
NEXT: PRINT ,
FOR i = a-3 TO a
IF d(i) = i THEN PRINT -d(i); ELSE PRINT d(i);
NEXT
WEND: PRINT: PRINT " = "; k, TIMER-z: END</lang>
bc
I provide a shuffle() function. It can only shuffle an array of numbers. It fails if the array has more than 32768 elements. It always shuffles the array named shuffle[]; the array is not a function parameter because bc passes arrays by copying.
This code requires a bc with long names; the test program also requires a bc with the print statement.
<lang bc>seed = 1 /* seed of the random number generator */ scale = 0
/* Random number from 0 to 32767. */ define rand() { /* Formula (from POSIX) for random numbers of low quality. */ seed = (seed * 1103515245 + 12345) % 4294967296 return ((seed / 65536) % 32768) }
/* Shuffle the first _count_ elements of shuffle[]. */ define shuffle(count) { auto b, i, j, t
i = count while (i > 0) { /* j = random number in [0, i) */ b = 32768 % i /* want rand() >= b */ while (1) { j = rand() if (j >= b) break } j = j % i
/* decrement i, swap shuffle[i] and shuffle[j] */ t = shuffle[--i] shuffle[i] = shuffle[j] shuffle[j] = t } }
/* Test program. */ define print_array(count) { auto i for (i = 0; i < count - 1; i++) print shuffle[i], ", " print shuffle[i], "\n" }
for (i = 0; i < 10; i++) shuffle[i] = 11 * (i + 1) "Original array: "; trash = print_array(10)
trash = shuffle(10) "Shuffled array: "; trash = print_array(10) quit</lang>
- Output:
Original array: 11, 22, 33, 44, 55, 66, 77, 88, 99, 110 Shuffled array: 66, 44, 11, 55, 33, 77, 110, 22, 88, 99
BQN
BQN's arrays are immutable, but variable values can be changed using the `↩` symbol. This program repeatedly changes the array's value using under.
<lang bqn>Knuth ← {
𝕊 arr:
l ← ≠arr
{
arr ↩ ⌽⌾(⟨•rand.Range l, 𝕩⟩⊸⊏)arr
}¨↕l
arr
} P ← •Show Knuth
P ⟨⟩ P ⟨10⟩ P ⟨10, 20⟩ P ⟨10, 20, 30⟩</lang>
Brat
<lang brat>shuffle = { a |
(a.length - 1).to 1 { i |
random_index = random(0, i)
temp = a[i]
a[i] = a[random_index]
a[random_index] = temp
}
a
}
p shuffle [1 2 3 4 5 6 7]</lang>
C
This shuffles any "object"; it imitates qsort in the syntax. <lang c>#include <stdlib.h>
- include <string.h>
int rrand(int m) {
return (int)((double)m * ( rand() / (RAND_MAX+1.0) ));
}
- define BYTE(X) ((unsigned char *)(X))
void shuffle(void *obj, size_t nmemb, size_t size) {
void *temp = malloc(size);
size_t n = nmemb;
while ( n > 1 ) {
size_t k = rrand(n--);
memcpy(temp, BYTE(obj) + n*size, size);
memcpy(BYTE(obj) + n*size, BYTE(obj) + k*size, size);
memcpy(BYTE(obj) + k*size, temp, size);
}
free(temp);
} </lang> Alternatively, using Durstenfeld's method (swapping selected item and last item in each iteration instead of literally shifting everything), and macro'd function declaration/definition: <lang C>#include <stdio.h>
- include <stdlib.h>
/* define a shuffle function. e.g. decl_shuffle(double).
* advantage: compiler is free to optimize the swap operation without * indirection with pointers, which could be much faster. * disadvantage: each datatype needs a separate instance of the function. * for a small funciton like this, it's not very big a deal. */
- define decl_shuffle(type) \
void shuffle_##type(type *list, size_t len) { \ int j; \ type tmp; \ while(len) { \ j = irand(len); \ if (j != len - 1) { \ tmp = list[j]; \ list[j] = list[len - 1]; \ list[len - 1] = tmp; \ } \ len--; \ } \ } \
/* random integer from 0 to n-1 */ int irand(int n) { int r, rand_max = RAND_MAX - (RAND_MAX % n); /* reroll until r falls in a range that can be evenly * distributed in n bins. Unless n is comparable to * to RAND_MAX, it's not *that* important really. */ while ((r = rand()) >= rand_max); return r / (rand_max / n); }
/* declare and define int type shuffle function from macro */ decl_shuffle(int);
int main() { int i, x[20];
for (i = 0; i < 20; i++) x[i] = i; for (printf("before:"), i = 0; i < 20 || !printf("\n"); i++) printf(" %d", x[i]);
shuffle_int(x, 20);
for (printf("after: "), i = 0; i < 20 || !printf("\n"); i++) printf(" %d", x[i]); return 0; }</lang>
C#
<lang csharp>public static void KnuthShuffle<T>(T[] array) {
System.Random random = new System.Random();
for (int i = 0; i < array.Length; i++)
{
int j = random.Next(i, array.Length); // Don't select from the entire array on subsequent loops
T temp = array[i]; array[i] = array[j]; array[j] = temp;
}
}</lang>
C++
Compiler: g++ (version 4.3.2 20081105 (Red Hat 4.3.2-7)) <lang cpp>#include <cstdlib>
- include <algorithm>
- include <iterator>
template<typename RandomAccessIterator> void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
for(unsigned int n = end - begin - 1; n >= 1; --n) {
unsigned int k = rand() % (n + 1);
if(k != n) {
std::iter_swap(begin + k, begin + n);
}
}
}</lang>
The standard library provides this in the form of std::random_shuffle.
<lang cpp>#include <algorithm>
- include <vector>
int main() {
int array[] = { 1,2,3,4,5,6,7,8,9 }; // C-style array of integers
std::vector<int> vec(array, array + 9); // build STL container from int array
std::random_shuffle(array, array + 9); // shuffle C-style array std::random_shuffle(vec.begin(), vec.end()); // shuffle STL container
}</lang>
Clojure
<lang lisp>(defn shuffle [vect]
(reduce (fn [v i] (let [r (rand-int i)]
(assoc v i (v r) r (v i))))
vect (range (dec (count vect)) 1 -1)))</lang>
This works by generating a sequence of end-indices from n-1 to 1, then reducing that sequence (starting with the original vector) through a function that, given a vector and end-index, performs a swap between the end-index and some random index less than the end-index.
CLU
<lang clu>knuth_shuffle = proc [T: type] (a: array[T])
lo: int := array[T]$low(a)
hi: int := array[T]$high(a)
for i: int in int$from_to_by(hi, lo+1, -1) do
j: int := lo + random$next(i-lo+1)
temp: T := a[i]
a[i] := a[j]
a[j] := temp
end
end knuth_shuffle
start_up = proc ()
po: stream := stream$primary_output()
d: date := now()
random$seed(d.second + 60*(d.minute + 60*d.hour))
arr: array[int] := array[int]$[1,2,3,4,5,6,7,8,9]
knuth_shuffle[int](arr)
for i: int in array[int]$elements(arr) do
stream$puts(po, int$unparse(i) || " ")
end
end start_up</lang>
- Output:
7 9 2 3 4 8 1 6 5
(Or any other order.)
CMake
<lang cmake># shuffle(<output variable> [<value>...]) shuffles the values, and
- stores the result in a list.
function(shuffle var)
set(forever 1)
# Receive ARGV1, ARGV2, ..., ARGV${last} as an array of values.
math(EXPR last "${ARGC} - 1")
# Shuffle the array with Knuth shuffle (Fisher-Yates shuffle).
foreach(i RANGE ${last} 1)
# Roll j = a random number from 1 to i.
math(EXPR min "100000000 % ${i}")
while(forever)
string(RANDOM LENGTH 8 ALPHABET 0123456789 j)
if(NOT j LESS min) # Prevent modulo bias when j < min.
break() # Break loop when j >= min.
endif()
endwhile()
math(EXPR j "${j} % ${i} + 1")
# Swap ARGV${i} with ARGV${j}.
set(t ${ARGV${i}})
set(ARGV${i} ${ARGV${j}})
set(ARGV${j} ${t})
endforeach(i)
# Convert array to list.
set(answer)
foreach(i RANGE 1 ${last})
list(APPEND answer ${ARGV${i}})
endforeach(i)
set("${var}" ${answer} PARENT_SCOPE)
endfunction(shuffle)</lang>
<lang cmake>shuffle(result 11 22 33 44 55 66) message(STATUS "${result}")
- One possible output:
- -- 66;33;22;55;44;11</lang>
COBOL
<lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. knuth-shuffle.
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 i PIC 9(8).
01 j PIC 9(8).
01 temp PIC 9(8).
LINKAGE SECTION.
78 Table-Len VALUE 10.
01 ttable-area.
03 ttable PIC 9(8) OCCURS Table-Len TIMES.
PROCEDURE DIVISION USING ttable-area.
MOVE FUNCTION RANDOM(FUNCTION CURRENT-DATE (11:6)) TO i
PERFORM VARYING i FROM Table-Len BY -1 UNTIL i = 0
COMPUTE j =
FUNCTION MOD(FUNCTION RANDOM * 10000, Table-Len) + 1
MOVE ttable (i) TO temp
MOVE ttable (j) TO ttable (i)
MOVE temp TO ttable (j)
END-PERFORM
GOBACK
.</lang>
CoffeeScript
<lang coffeescript>knuth_shuffle = (a) ->
n = a.length while n > 1 r = Math.floor(n * Math.random()) n -= 1 [a[n], a[r]] = [a[r], a[n]] a
counts =
"1,2,3": 0 "1,3,2": 0 "2,1,3": 0 "2,3,1": 0 "3,1,2": 0 "3,2,1": 0
for i in [1..100000]
counts[knuth_shuffle([ 1, 2, 3 ]).join(",")] += 1
for key, val of counts
console.log "#{key}: #{val}"</lang>
- Output:
> coffee knuth_shuffle.coffee 1,2,3: 16714 1,3,2: 16566 2,1,3: 16460 2,3,1: 16715 3,1,2: 16750 3,2,1: 16795
Common Lisp
<lang lisp>(defun nshuffle (sequence)
(loop for i from (length sequence) downto 2
do (rotatef (elt sequence (random i))
(elt sequence (1- i))))
sequence)</lang>
This operates on arbitrary sequences, but will be inefficient applied to a list as opposed to a vector. Dispatching on type, and using an intermediate vector to hold the contents of list can make both cases more efficient (since the array specific case can use aref rather than elt):
<lang lisp>(defun nshuffle (sequence)
(etypecase sequence (list (nshuffle-list sequence)) (array (nshuffle-array sequence))))
(defun nshuffle-list (list)
"Shuffle the list using an intermediate vector." (let ((array (nshuffle-array (coerce list 'vector)))) (declare (dynamic-extent array)) (map-into list 'identity array)))
(defun nshuffle-array (array)
(loop for i from (length array) downto 2
do (rotatef (aref array (random i))
(aref array (1- i)))
finally (return array)))</lang>
Crystal
<lang crystal>def knuthShuffle(items : Array)
i = items.size-1
while i > 1
j = Random.rand(0..i)
items.swap(i, j)
i -= 1 end
end</lang>
D
Standard Version
A variant of the Knuth shuffle is in the D standard library Phobos: <lang d>void main() {
import std.stdio, std.random;
auto a = [1, 2, 3, 4, 5, 6, 7, 8, 9]; a.randomShuffle; a.writeln;
}</lang>
- Output:
[8, 9, 3, 1, 7, 5, 4, 6, 2]
One Implementation
This shuffles any collection that supports random access, length and swapping of items: <lang d>import std.stdio, std.algorithm, std.random, std.range;
void knuthShuffle(Range)(Range r) if (isRandomAccessRange!Range && hasLength!Range &&
hasSwappableElements!Range) {
foreach_reverse (immutable i, ref ri; r[1 .. $ - 1])
ri.swap(r[uniform(0, i + 1)]);
}
void main() {
auto a = [1, 2, 3, 4, 5, 6, 7, 8, 9]; a.knuthShuffle; a.writeln;
}</lang>
Delphi
DWScript
<lang delphi>procedure KnuthShuffle(a : array of Integer); var
i, j, tmp : Integer;
begin
for i:=a.High downto 1 do begin
j:=RandomInt(a.Length);
tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;
end;
end;</lang>
E
<lang e>def shuffle(array, random) {
for bound in (2..(array.size())).descending() {
def i := random.nextInt(bound)
def swapTo := bound - 1
def t := array[swapTo]
array[swapTo] := array[i]
array[i] := t
}
}</lang> <lang e>? def arr := [1,2,3,4,5,6,7,8,9,10].diverge()
- value: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].diverge()
? shuffle(arr, entropy) ? arr
- value: [4, 5, 2, 9, 7, 8, 1, 3, 6, 10].diverge()</lang>
EasyLang
<lang>func shuffle . a[] .
for i = len a[] downto 2 r = random i swap a[r] a[i - 1] .
. arr[] = [ 1 2 3 ] call shuffle arr[] print arr[] </lang>
EchoLisp
<lang scheme> Remark- The native shuffle function implementation in EchoLisp has been replaced by this one.
Thx Rosetta Code.
(lib 'list) ;; for list-permute
- use "inside-out" algorithm, no swapping needed.
- returns a random permutation vector of [0 .. n-1]
(define (rpv n (j)) (define v (make-vector n)) (for [(i n)] (set! j (random (1+ i))) (when (!= i j) (vector-set! v i [v j])) (vector-set! v j i)) v)
- apply to any kind of list
(define (k-shuffle list) (list-permute list (vector->list (rpv (length list)))))
- out
(k-shuffle (iota 17))
→ (16 7 11 10 0 9 15 12 13 8 4 2 14 3 6 5 1)
(k-shuffle '(adrien 🎸 alexandre 🚂 antoine 🍼 ben 📚 georges 📷 julie 🎥 marine 🐼 nathalie 🍕 ))
→ (marine alexandre 🎥 julie 🎸 ben 🍼 nathalie 📚 georges 🚂 antoine adrien 🐼 📷 🍕)
(shuffle ;; native '(adrien 🎸 alexandre 🚂 antoine 🍼 ben 📚 georges 📷 julie 🎥 marine 🐼 nathalie 🍕 ))
→ (antoine 🎥 🚂 marine adrien nathalie 🍼 🍕 ben 🐼 julie 📷 📚 🎸 alexandre georges)
</lang>
Egel
<lang Egel> import "prelude.eg" import "random.ego"
using System using List using Math
def swap =
[ I J XX -> insert I (nth J XX) (insert J (nth I XX) XX) ]
def shuffle =
[ XX ->
let INDICES = reverse (fromto 0 ((length XX) - 1)) in
let SWAPS = map [ I -> I (between 0 I) ] INDICES in
foldr [I J -> swap I J] XX SWAPS ]
def main = shuffle (fromto 1 9) </lang>
Eiffel
<lang Eiffel> class APPLICATION
create make
feature {NONE} -- Initialization
make do test := <<1, 2>> io.put_string ("Initial: ") across test as t loop io.put_string (t.item.out + " ") end test := shuffle (test) io.new_line io.put_string ("Shuffled: ") across test as t loop io.put_string (t.item.out + " ") end end
test: ARRAY [INTEGER]
shuffle (ar: ARRAY [INTEGER]): ARRAY [INTEGER] -- Array containing the same elements as 'ar' in a shuffled order. require more_than_one_element: ar.count > 1 local count, j, ith: INTEGER random: V_RANDOM do create random create Result.make_empty Result.deep_copy (ar) count := ar.count across 1 |..| count as c loop j := random.bounded_item (c.item, count) ith := Result [c.item] Result [c.item] := Result [j] Result [j] := ith random.forth end ensure same_elements: across ar as a all Result.has (a.item) end end
end
</lang>
- Output:
Initial: 1 2 3 4 5 6 7 Shuffeld: 1 5 3 4 7 6 2
Elena
ELENA 4.x: <lang elena>import system'routines; import extensions;
const int MAX = 10;
extension randomOp {
randomize()
{
var max := self.Length;
for(int i := 0, i < max, i += 1)
{
var j := randomGenerator.eval(i,max);
self.exchange(i,j)
};
^ self
}
}
public program() {
var a := Array.allocate:MAX.populate:(i => i ); console.printLine(a.randomize())
}</lang>
- Output:
7,3,6,8,4,9,0,1,2,5
Elixir
<lang elixir>defmodule Knuth do
def shuffle( inputs ) do
n = length( inputs )
{[], acc} = Enum.reduce( n..1, {inputs, []}, &random_move/2 )
acc
end
defp random_move( n, {inputs, acc} ) do
item = Enum.at( inputs, :rand.uniform(n)-1 )
{List.delete( inputs, item ), [item | acc]}
end
end
seq = Enum.to_list( 0..19 ) IO.inspect Knuth.shuffle( seq )
seq = [1,2,3] Enum.reduce(1..100000, Map.new, fn _,acc ->
k = Knuth.shuffle(seq) Map.update(acc, k, 1, &(&1+1))
end) |> Enum.each(fn {k,v} -> IO.inspect {k,v} end)</lang>
- Output:
[17, 13, 4, 2, 16, 1, 8, 19, 9, 12, 14, 5, 0, 11, 6, 10, 18, 3, 15, 7]
{[1, 2, 3], 16702}
{[1, 3, 2], 16635}
{[2, 1, 3], 16518}
{[2, 3, 1], 16935}
{[3, 1, 2], 16500}
{[3, 2, 1], 16710}
Erlang
<lang Erlang> -module( knuth_shuffle ).
-export( [list/1] ).
list( Inputs ) -> N = erlang:length( Inputs ), {[], Acc} = lists:foldl( fun random_move/2, {Inputs, []}, lists:reverse(lists:seq(1, N)) ), Acc.
random_move( N, {Inputs, Acc} ) -> Item = lists:nth( random:uniform(N), Inputs ), {lists:delete(Item, Inputs), [Item | Acc]}. </lang>
- Output:
21> knuth_shuffle:list(lists:seq(1,9)). [5,7,8,1,4,2,3,9,6]
ERRE
<lang ERRE>PROGRAM KNUTH_SHUFFLE
CONST CARDS%=52
DIM PACK%[CARDS%]
BEGIN
RANDOMIZE(TIMER)
FOR I%=1 TO CARDS% DO
PACK%[I%]=I%
END FOR
FOR N%=CARDS% TO 2 STEP -1 DO
SWAP(PACK%[N%],PACK%[1+INT(N%*RND(1))])
END FOR
FOR I%=1 TO CARDS% DO
PRINT(PACK%[I%];)
END FOR
PRINT
END PROGRAM </lang>
Euphoria
<lang Euphoria>sequence cards cards = repeat(0,52) integer card,temp
puts(1,"Before:\n") for i = 1 to 52 do
cards[i] = i printf(1,"%d ",cards[i])
end for
for i = 52 to 1 by -1 do
card = rand(i)
if card != i then
temp = cards[card]
cards[card] = cards[i]
cards[i] = temp
end if
end for
puts(1,"\nAfter:\n") for i = 1 to 52 do
printf(1,"%d ",cards[i])
end for</lang>
F#
Allows a shuffle of arrays of arbitrary items. Requires 2010 beta of F#. Lazily returns a sequence.
This is the original Fisher-Yates shuffle as described by the link: <lang fsharp>open System
let FisherYatesShuffle (initialList : array<'a>) = // '
let availableFlags = Array.init initialList.Length (fun i -> (i, true))
// Which items are available and their indices
let rnd = new Random()
let nextItem nLeft =
let nItem = rnd.Next(0, nLeft) // Index out of available items
let index = // Index in original deck
availableFlags // Go through available array
|> Seq.filter (fun (ndx,f) -> f) // and pick out only the available tuples
|> Seq.nth nItem // Get the one at our chosen index
|> fst // and retrieve it's index into the original array
availableFlags.[index] <- (index, false) // Mark that index as unavailable
initialList.[index] // and return the original item
seq {(initialList.Length) .. -1 .. 1} // Going from the length of the list down to 1
|> Seq.map (fun i -> nextItem i) // yield the next item</lang>
Here's the modified Knuth shuffle which shuffles the original array in place <lang fsharp>let KnuthShuffle (lst : array<'a>) = // '
let Swap i j = // Standard swap
let item = lst.[i]
lst.[i] <- lst.[j]
lst.[j] <- item
let rnd = new Random()
let ln = lst.Length
[0..(ln - 2)] // For all indices except the last
|> Seq.iter (fun i -> Swap i (rnd.Next(i, ln))) // swap th item at the index with a random one following it (or itself)
lst // Return the list shuffled in place</lang>
Example: <lang fsharp>> KnuthShuffle [| "Darrell"; "Marvin"; "Doug"; "Greg"; "Sam"; "Ken" |];; val it : string array = [|"Marvin"; "Doug"; "Sam"; "Darrell"; "Ken"; "Greg"|]</lang>
Factor
There is a randomize word already in the standard library. Implementation:
<lang factor>: randomize ( seq -- seq )
dup length [ dup 1 > ] [ [ iota random ] [ 1 - ] bi [ pick exchange ] keep ] while drop ;</lang>
Fantom
<lang fantom>class Main {
static Void knuthShuffle (List array)
{
((array.size-1)..1).each |Int i|
{
r := Int.random(0..i)
array.swap (i, r)
}
}
public static Void main ()
{
List a := [1,2,3,4,5]
knuthShuffle (a)
echo (a)
List b := ["apples", "oranges", "pears", "bananas"] knuthShuffle (b) echo (b) }
}</lang>
Forth
<lang forth>include random.fs
- shuffle ( deck size -- )
2 swap do dup i random cells + over @ over @ swap rot ! over ! cell+ -1 +loop drop ;
- .array 0 do dup @ . cell+ loop drop ;
create deck 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,
deck 10 2dup shuffle .array</lang>
Fortran
<lang fortran>program Knuth_Shuffle
implicit none
integer, parameter :: reps = 1000000 integer :: i, n integer, dimension(10) :: a, bins = 0, initial = (/ (n, n=1,10) /)
do i = 1, reps a = initial call Shuffle(a) where (a == initial) bins = bins + 1 ! skew tester end do write(*, "(10(i8))") bins
! prints 100382 100007 99783 100231 100507 99921 99941 100270 100290 100442
contains
subroutine Shuffle(a)
integer, intent(inout) :: a(:) integer :: i, randpos, temp real :: r
do i = size(a), 2, -1
call random_number(r)
randpos = int(r * i) + 1
temp = a(randpos)
a(randpos) = a(i)
a(i) = temp
end do
end subroutine Shuffle
end program Knuth_Shuffle</lang>
FreeBASIC
<lang freebasic>' version 22-10-2016 ' compile with: fbc -s console ' for boundry checks on array's compile with: fbc -s console -exx
' sort from lower bound to the highter bound ' array's can have subscript range from -2147483648 to +2147483647
Sub knuth_down(a() As Long)
Dim As Long lb = LBound(a) Dim As ULong n = UBound(a) - lb +1 Dim As ULong i, j
Randomize Timer
For i = n -1 To 1 Step -1
j =Fix(Rnd * (i +1)) ' 0 <= j <= i
Swap a(lb + i), a(lb + j)
Next
End Sub
Sub knuth_up(a() As Long)
Dim As Long lb = LBound(a) Dim As ULong n = UBound(a) - lb +1 Dim As ULong i, j
Randomize Timer
For i = 0 To n -2
j = Fix(Rnd * (n - i) + i) ' 0 <= j < n-i, + i ==> i <= j < n
Swap a(lb + i), a(lb + j)
Next
End Sub
' ------=< MAIN >=------
Dim As Long i Dim As Long array(1 To 52), array2(-7 To 7)
For i = 1 To 52 : array(i) = i : Next
Print "Starting array" For i = 1 To 52
Print Using " ###";array(i);
Next : Print : Print
knuth_down(array())
Print "After Knuth shuffle downwards" For i = 1 To 52
Print Using " ###";array(i);
Next : Print : Print
For i = LBound(array2) To UBound(array2)
array2(i) = i - LBound(array2) + 1
Next
Print "Starting array, first index <> 0 " For i = LBound(array2) To UBound(array2)
Print Using " ##";array2(i);
Next : Print : Print
knuth_up(array2()) Print "After Knuth shuffle upwards" For i = LBound(array2) To UBound(array2)
Print Using " ##";array2(i);
Next : Print : Print
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</lang>
- Output:
Starting array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 After Knuth shuffle downwards 2 17 46 4 40 36 51 24 19 29 13 9 8 16 44 43 47 34 14 52 39 35 23 31 48 42 7 12 21 33 18 32 22 49 38 6 27 1 41 5 20 15 37 3 28 30 26 45 50 25 10 11 Starting array, first index <> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 After Knuth shuffle upwards 4 1 9 10 15 11 12 7 3 5 8 13 6 14 2
Frink
The built-in method array.shuffle[] implements the Fisher-Yates-Knuth shuffle algorithm:
<lang frink>
a = [1,2,3]
a.shuffle[]
</lang>
FunL
<lang funl>def shuffle( a ) =
res = array( a ) n = a.length() for i <- 0:n r = rnd( i:n ) res(i), res(r) = res(r), res(i) res.toList()</lang>
Gambas
Click this link to run this code <lang gambas>Public Sub Main() Dim iTotal As Integer = 40 Dim iCount, iRand1, iRand2 As Integer Dim iArray As New Integer[]
For iCount = 0 To iTotal
iArray.add(iCount)
Next
Print "Original = "; For iCount = 0 To iArray.Max
If iCount = iArray.max Then Print iArray[iCount]; Else Print iArray[iCount] & ",";
Next
For iCount = iTotal DownTo 0
iRand1 = Rand(iTotal) iRand2 = Rand(iTotal) Swap iArray[iRand1], iArray[iRand2]
Next
Print gb.NewLine & "Shuffled = "; For iCount = 0 To iArray.Max
If iCount = iArray.max Then Print iArray[iCount]; Else Print iArray[iCount] & ",";
Next
End</lang> Output:
Original = 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40 Shuffled = 8,23,12,31,4,38,39,40,37,34,14,0,21,22,3,10,27,26,17,15,6,7,19,2,24,35,25,16,18,36,1,13,32,33,20,5,9,11,29,28,30
GAP
<lang gap># Return the list L after applying Knuth shuffle. GAP also has the function Shuffle, which does the same. ShuffleAlt := function(a)
local i, j, n, t;
n := Length(a);
for i in [n, n - 1 .. 2] do
j := Random(1, i);
t := a[i];
a[i] := a[j];
a[j] := t;
od;
return a;
end;
- Return a "Permutation" object (a permutation of 1 .. n).
- They are printed in GAP, in cycle decomposition form.
PermShuffle := n -> PermList(ShuffleAlt([1 .. n]));
ShuffleAlt([1 .. 10]);
- [ 4, 7, 1, 5, 8, 2, 6, 9, 10, 3 ]
PermShuffle(10);
- (1,9)(2,3,6,4,5,10,8,7)
- One may also call the built-in random generator on the symmetric group :
Random(SymmetricGroup(10)); (1,8,2,5,9,6)(3,4,10,7)</lang>
Go
(Note, in addition to these examples,
rand.Shuffle
was added in Go1.10
implementing a Fisher–Yates shuffle.)
<lang go>package main
import (
"fmt" "math/rand" "time"
)
func main() {
var a [20]int
for i := range a {
a[i] = i
}
fmt.Println(a)
rand.Seed(time.Now().UnixNano())
for i := len(a) - 1; i >= 1; i-- {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
fmt.Println(a)
}</lang> To shuffle any type: <lang go>package main
import (
"fmt" "math/rand" "time"
)
// Generic Knuth Shuffle algorithm. In Go, this is done with interface // types. The parameter s of function shuffle is an interface type. // Any type satisfying the interface "shuffler" can be shuffled with // this function. Since the shuffle function uses the random number // generator, it's nice to seed the generator at program load time. func init() {
rand.Seed(time.Now().UnixNano())
} func shuffle(s shuffler) {
for i := s.Len() - 1; i >= 1; i-- {
j := rand.Intn(i + 1)
s.Swap(i, j)
}
}
// Conceptually, a shuffler is an indexed collection of things. // It requires just two simple methods. type shuffler interface {
Len() int // number of things in the collection Swap(i, j int) // swap the two things indexed by i and j
}
// ints is an example of a concrete type implementing the shuffler // interface. type ints []int
func (s ints) Len() int { return len(s) } func (s ints) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
// Example program. Make an ints collection, fill with sequential numbers, // print, shuffle, print. func main() {
a := make(ints, 20)
for i := range a {
a[i] = i
}
fmt.Println(a)
shuffle(a)
fmt.Println(a)
}</lang>
- Example output:
(of either program)
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] [11 10 12 19 4 13 15 17 14 2 5 18 8 0 6 9 7 3 1 16]
Groovy
Solution: <lang groovy>def shuffle = { list ->
if (list == null || list.empty) return list
def r = new Random()
def n = list.size()
(n..1).each { i ->
def j = r.nextInt(i)
listi-1, j = listj, i-1
}
list
}</lang> Test: <lang groovy>def list = [] + (0..20) println list println shuffle(list) println shuffle(list) println shuffle(list)</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [12, 16, 7, 13, 1, 9, 17, 20, 15, 3, 5, 6, 8, 0, 18, 10, 14, 4, 2, 11, 19] [17, 6, 10, 1, 18, 5, 7, 13, 2, 11, 16, 3, 14, 0, 4, 20, 19, 12, 8, 9, 15] [6, 20, 11, 4, 7, 12, 5, 14, 19, 18, 13, 15, 1, 2, 8, 16, 17, 10, 0, 9, 3]
Haskell
<lang Haskell>import System.Random (randomRIO)
mkRands :: Int -> IO [Int] mkRands = mapM (randomRIO . (,) 0) . enumFromTo 1 . pred
replaceAt :: Int -> a -> [a] -> [a] replaceAt i c l =
let (a, b) = splitAt i l in a ++ c : drop 1 b
swapElems :: (Int, Int) -> [a] -> [a] swapElems (i, j) xs
| i == j = xs | otherwise = replaceAt j (xs !! i) $ replaceAt i (xs !! j) xs
knuthShuffle :: [a] -> IO [a] knuthShuffle xs = (foldr swapElems xs . zip [1 ..]) <$> mkRands (length xs)</lang>
or, as an alternative to making two indexed references into the list with (!!): <lang haskell>import System.Random (randomRIO) import Data.Bool (bool)
knuthShuffle :: [a] -> IO [a] knuthShuffle xs = (foldr swapped xs . zip [1 ..]) <$> randoms (length xs)
swapped :: (Int, Int) -> [a] -> [a] swapped (i, j) xs =
let go (a, b)
| a == b = xs
| otherwise =
let (m, n) = bool (b, a) (a, b) (b > a)
(l, hi:t) = splitAt m xs
(ys, lo:zs) = splitAt (pred (n - m)) t
in concat [l, lo : ys, hi : zs]
in bool xs (go (i, j)) $ ((&&) . (i <) <*> (j <)) $ length xs
randoms :: Int -> IO [Int] randoms x = mapM (randomRIO . (,) 0) [1 .. pred x]
main :: IO () main = knuthShuffle ['a' .. 'k'] >>= print</lang>
Examples of use of either of the two versions above:
*Main> knuthShuffle ['a'..'k'] "bhjdgfciake" *Main> knuthShuffle $ map(ap (,)(+10)) [0..9] [(0,10),(8,18),(2,12),(3,13),(9,19),(4,14),(7,17),(1,11),(6,16),(5,15)]
Function for showing intermediate results: <lang Haskell>knuthShuffleProcess :: (Show a) => [a] -> IO () knuthShuffleProcess =
(mapM_ print. reverse =<<). ap (fmap. (. zip [1..]). scanr swapElems) (mkRands. length)</lang>
- Output:
Detailed example
*Main> knuthShuffleProcess ['a'..'k'] "abcdefghijk" "abckefghijd" "jbckefghiad" "jbckeighfad" "jbckeihgfad" "jbhkeicgfad" "jbhiekcgfad" "jbeihkcgfad" "ibejhkcgfad" "iebjhkcgfad" "iebjhkcgfad"
An imperative implementation using arrays and the ST monad:
<lang haskell>import Data.Array.ST
import Data.STRef
import Control.Monad
import Control.Monad.ST
import Control.Arrow
import System.Random
shuffle :: RandomGen g => [a] -> g -> ([a], g) shuffle list g = runST $ do
r <- newSTRef g
let rand range = liftM (randomR range) (readSTRef r) >>=
runKleisli (second (Kleisli $ writeSTRef r) >>> arr fst)
a <- newAry (1, len) list
forM_ [len, len - 1 .. 2] $ \n -> do
k <- rand (1, n)
liftM2 (,) (readArray a k) (readArray a n) >>=
runKleisli (Kleisli (writeArray a n) *** Kleisli (writeArray a k))
liftM2 (,) (getElems a) (readSTRef r)
where len = length list
newAry :: (Int, Int) -> [a] -> ST s (STArray s Int a)
newAry = newListArray</lang>
Icon and Unicon
The shuffle method used here can shuffle lists, record fields, and strings: <lang icon>procedure main()
show(shuffle([3,1,4,1,5,9,2,6,3]))
show(shuffle("this is a string"))
end
procedure shuffle(A)
every A[i := *A to 1 by -1] :=: A[?i] return A
end
procedure show(A)
every writes(!A," ") write()
end</lang>
- Output:
->ks 9 6 1 4 3 1 3 5 2 i n t i s r t g h s a i s ->
Note that the gloriously succinct 'standard' Icon shuffle: <lang icon>procedure shuffle(A)
every !A :=: ?A
end</lang> is subtly biased.
Inform 6
<lang Inform 6>[ shuffle a n i j tmp;
for(i = n - 1: i > 0: i--)
{
j = random(i + 1) - 1;
tmp = a->j; a->j = a->i; a->i = tmp; }
];</lang>
J
<lang j>KS=:{~ (2&{.@[ {`(|.@[)`]} ])/@(,~(,.?@>:))@i.@#</lang> The input array is transformed to a rectangular array of indexes. By doing this all kinds of arrays can serve as input (see examples below). The process is imitated by using using a fold, swapping elements in a restricted part of this index-array in each fold step. <lang j>process J
fold swap transform array <==> f / g y</lang>
Example of a transformed input: <lang j>(,~(,.?@>:))@i.@# 1+i.6 0 0 0 0 0 0 1 1 0 0 0 0 2 0 0 0 0 0 3 2 0 0 0 0 4 3 0 0 0 0 5 0 0 0 0 0 0 1 2 3 4 5</lang> The last row is the index-array that has to be shuffled. The other rows have valid indexes in the first two columns. The second column has a randomized value <= value first column.
The index-swapping is done by the part: <lang j>2&{.@[ {`(|.@[)`]} ]</lang> Finally, the shuffled indexes select elements from the original array. <lang j>input { ~ shuffled indexes</lang> Alternatively, instead of creating a rectangular array, the swapping indices and the original data can be individually boxed.
In other words, (,~ (,. ?@>:))@i.@# can be replaced with |.@; ;&~./@(,. ?@>:)@i.@#, and the swapping can be achieved using (<@C. >)/ instead of (2&{.@[ {`(|.@[)`]} ])/.
With this approach, the data structure with the swapping indices and the original data could look like this:
<lang j> (|.@; ;&~./@(,. ?@>:)@i.@#)'abcde'
+---+-+---+---+-+-----+
|4 2|3|2 1|1 0|0|abcde|
+---+-+---+---+-+-----+</lang>
Note that we have the original data here, instead of indices to select all of its items. Note also that we have only a single value in a box where an item is being "swapped" with itself (this is required by J's cycle operation (C.)).
The resulting definition looks like this: <lang j>KS=: [: > (<@C. >)/@(|.@; ;&~./@(,. ?@>:)@i.@#)</lang> Note that here we did not wind up with a list of indices which we used to permute the original data set. That data set is permuted directly. However, it is in a box and we do have to remove it from that box.
Permuting the data directly, instead of permuting indices, has performance implications when the items being swapped are large, but see the note at the end of this entry for J for how you would do this operation in a "real" J program.
Examples:<lang j>]A=: 5+i.9 5 6 7 8 9 10 11 12 13</lang> Shuffle: <lang j>KS A 13 10 7 5 11 9 8 6 12</lang>Input <lang j>]M=: /:~(1 2 3,:2 3 4),(11 2 3,: 0 11 2),(1 1 1,:1 0),:1 1 1,:1 0 1
1 1 1 1 0 0
1 1 1 1 0 1
1 2 3 2 3 4
11 2 3
0 11 2</lang>Shuffle
<lang j>KS M 11 2 3
0 11 2
1 1 1 1 0 1
1 1 1 1 0 0
1 2 3 2 3 4</lang>Input
<lang j>]L=:'aA';'bbB';'cC%$';'dD@' +--+---+----+---+ |aA|bbB|cC%$|dD@| +--+---+----+---+</lang>Shuffle <lang j>KS L +--+----+---+---+ |aA|cC%$|dD@|bbB| +--+----+---+---+</lang> In J the shuffling of an arbitrary array can easily be implemented by the phrase ( ref http://www.jsoftware.com/jwiki/JPhrases/RandomNumbers ): <lang j>({~?~@#)</lang> Applied on the former examples: <lang j>({~?~@#) A 8 7 13 6 10 11 5 9 12
({~?~@#) M
1 1 1
1 0 1
1 2 3 2 3 4
11 2 3
0 11 2
1 1 1 1 0 0
({~?~@#) L
+----+---+--+---+ |cC%$|bbB|aA|dD@| +----+---+--+---+</lang>
Java
<lang java>import java.util.Random;
public static final Random gen = new Random();
// version for array of ints public static void shuffle (int[] array) {
int n = array.length;
while (n > 1) {
int k = gen.nextInt(n--); //decrements after using the value
int temp = array[n];
array[n] = array[k];
array[k] = temp;
}
} // version for array of references public static void shuffle (Object[] array) {
int n = array.length;
while (n > 1) {
int k = gen.nextInt(n--); //decrements after using the value
Object temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}</lang>
JavaScript
ES5
<lang javascript>function knuthShuffle(arr) {
var rand, temp, i;
for (i = arr.length - 1; i > 0; i -= 1) {
rand = Math.floor((i + 1) * Math.random());//get random between zero and i (inclusive)
temp = arr[rand];//swap i and the zero-indexed number
arr[rand] = arr[i];
arr[i] = temp;
}
return arr;
}
var res = {
'1,2,3': 0, '1,3,2': 0, '2,1,3': 0, '2,3,1': 0, '3,1,2': 0, '3,2,1': 0
};
for (var i = 0; i < 100000; i++) {
res[knuthShuffle([1,2,3]).join(',')] += 1;
}
for (var key in res) {
print(key + "\t" + res[key]);
}</lang> Results in:
1,2,3 16619 1,3,2 16614 2,1,3 16752 2,3,1 16959 3,1,2 16460 3,2,1 16596
ES6
Mutating in-place swap
<lang JavaScript>(() => {
// knuthShuffle :: [a] -> [a]
const knuthShuffle = xs =>
enumFromTo(0, xs.length - 1)
.reduceRight((a, i) => {
const
iRand = randomRInt(0, i),
tmp = a[iRand];
return iRand !== i ? (
a[iRand] = a[i],
a[i] = tmp,
a
) : a;
}, xs);
const test = () => knuthShuffle(
(`alpha beta gamma delta epsilon zeta
eta theta iota kappa lambda mu`)
.split(/\s+/)
);
// GENERIC FUNCTIONS ----------------------------------
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
n >= m ? (
iterateUntil(x => x >= n, x => 1 + x, m)
) : [];
// iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
const iterateUntil = (p, f, x) => {
let vs = [x],
h = x;
while (!p(h))(h = f(h), vs.push(h));
return vs;
};
// randomRInt :: Int -> Int -> Int
const randomRInt = (low, high) =>
low + Math.floor(
(Math.random() * ((high - low) + 1))
);
return test();
})(); </lang>
- Output:
e.g. <lang JavaScript>["iota", "epsilon", "kappa", "theta", "gamma", "delta", "lambda", "eta", "zeta", "beta", "mu", "alpha"]</lang>
Non-mutating swap
<lang JavaScript>(() => {
// knuthShuffle :: [a] -> [a]
const knuthShuffle = xs =>
enumFromTo(0, xs.length - 1)
.reduceRight((a, i) => {
const iRand = randomRInt(0, i);
return i !== iRand ? (
swapped(i, iRand, a)
) : a;
}, xs);
const test = () => knuthShuffle(
(`alpha beta gamma delta epsilon zeta
eta theta iota kappa lambda mu`)
.split(/\s+/)
);
// Non mutating version of swapped
// swapped :: Int -> Int -> [a] -> [a]
const swapped = (iFrom, iTo, xs) =>
xs.map(
(x, i) => iFrom !== i ? (
iTo !== i ? (
x
) : xs[iFrom]
) : xs[iTo]
);
// GENERIC FUNCTIONS ----------------------------------
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
n >= m ? (
iterateUntil(x => x >= n, x => 1 + x, m)
) : [];
// iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
const iterateUntil = (p, f, x) => {
let vs = [x],
h = x;
while (!p(h))(h = f(h), vs.push(h));
return vs;
};
// randomRInt :: Int -> Int -> Int
const randomRInt = (low, high) =>
low + Math.floor(
(Math.random() * ((high - low) + 1))
);
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = (f, xs, ys) =>
Array.from({
length: Math.min(xs.length, ys.length)
}, (_, i) => f(xs[i], ys[i], i));
// MAIN --- return test();
})();</lang>
- Output:
e.g. <lang JavaScript>["mu", "theta", "beta", "eta", "delta", "epsilon", "kappa", "alpha", "gamma", "lambda", "zeta", "iota"]</lang>
Joy
<lang Joy>DEFINE knuth-shuffle ==
(* Take the size of the array (without destroying it) *) dup dup size
(* Generate a list of as many random numbers *) [rand] [rem] enconcat map
(* Zip the two lists *) swap zip
(* Sort according to the new index number *) [small] [] [uncons unswonsd [first >] split [swons] dip2] [enconcat] binrec
(* Delete the new index number *) [second] map.</lang> Using knuth-shuffle (file shuffle.joy): <lang Joy>(* Sorted array of 21 integers *) [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20] knuth-shuffle.</lang> Command line:
- joy shuffle.joy
- Output:
usrlib is loaded inilib is loaded agglib is loaded [12 6 8 4 14 18 7 15 1 0 11 13 5 10 16 2 19 17 9 20 3]
jq
Works with gojq, the Go implementation of jq
Neither the C nor the Go implementations of jq has a built-in PRNG, but both are designed with the Unix toolset philosophy in mind, so in this entry we will use an external source of randomness rather than one of the PRNGs defined in jq as at RC.
Specifically, we will use /dev/urandom like so:
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -RMnrc -f program.jq
where program.jq is the following program: <lang jq>
- 52-card deck:
def deck:
[range(127137; 127148), range(127149; 127151), # Spades range(127153; 127164), range(127165; 127167), # Hearts range(127169; 127180), range(127181; 127183), # Diamonds range(127185; 127196), range(127197; 127199)] # Clubs ;
- For splitting a deck into hands :-)
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; n;
- Output: a prn in range(0;$n) where $n is ., and $n > 0
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
def knuthShuffle:
length as $n
| if $n <= 1 then .
else {i: $n, a: .}
| until(.i == 0;
.i += -1
| (.i + 1 | prn) as $j
| .a[.i] as $t
| .a[.i] = .a[$j]
| .a[$j] = $t)
| .a
end;
def task:
[], [10,20], [10,20,30] | knuthShuffle;
task,
(deck|knuthShuffle | nwise(13) | implode)
</lang>
- Output:
[] [10,20] [20,30,10]
🂶🃚🃈🃘🃊🂥🃉🂽🂣🂸🃂🂺🃗
🂵🃁🃇🂮🂹🃝🃆🂱🂻🂩🃋🂭🃖
🂢🃛🃕🃃🂾🃙🃞🂨🂪🂲🂷🃍🂫
🂦🃒🃔🂳🂡🃓🃄🂴🃅🃎🃑🂤🂧
Julia
<lang julia>function knuthshuffle!(r::AbstractRNG, v::AbstractVector)
for i in length(v):-1:2
j = rand(r, 1:i)
v[i], v[j] = v[j], v[i]
end
return v
end knuthshuffle!(v::AbstractVector) = knuthshuffle!(Base.Random.GLOBAL_RNG, v)
v = collect(1:20) println("# v = $v\n -> ", knuthshuffle!(v))</lang>
- Output:
# v = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] -> [16, 5, 17, 10, 2, 7, 20, 14, 4, 8, 19, 15, 18, 12, 11, 1, 9, 13, 3, 6]
Kotlin
<lang scala>object Knuth {
internal val gen = java.util.Random()
}
fun <T> Array<T>.shuffle(): Array<T> {
val a = clone()
var n = a.size
while (n > 1) {
val k = Knuth.gen.nextInt(n--)
val t = a[n]
a[n] = a[k]
a[k] = t
}
return a
}
fun main(args: Array<String>) {
val str = "abcdefghijklmnopqrstuvwxyz".toCharArray()
(1..10).forEach {
val s = str.toTypedArray().shuffle().toCharArray()
println(s)
require(s.toSortedSet() == str.toSortedSet())
}
val ia = arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
(1..10).forEach {
val s = ia.shuffle()
println(s.distinct())
require(s.toSortedSet() == ia.toSet())
}
}</lang>
- Output:
xdhsvtnumjgbywiqoapcelkrfz pjnegbiyzuhsrclodftwkmaqvx bkmqwhzregifyanvsltxjupodc ewhxrlybnjqpvdsozaimkucgft pdqgoaymbzefnjrwuvilsckxht kcpagyuehjswdtvnzfrlbxqomi iztsmaygkblephcjfnwvxurdoq pltdyjwivsehckzfaxruqogmbn nytfbpmjicgkaueoxwrhlsqvdz epucijbvrhwyzdlsqftagxmkon [7, 4, 5, 9, 2, 1, 3, 8, 10, 6] [8, 10, 5, 4, 3, 6, 1, 2, 7, 9] [7, 9, 2, 1, 10, 4, 6, 5, 8, 3] [9, 6, 1, 8, 2, 5, 10, 3, 4, 7] [7, 3, 6, 9, 10, 2, 5, 4, 1, 8] [2, 9, 1, 7, 5, 10, 8, 4, 6, 3] [4, 2, 7, 3, 8, 5, 6, 10, 1, 9] [4, 8, 7, 6, 10, 5, 2, 1, 3, 9] [6, 3, 9, 4, 5, 2, 10, 8, 1, 7] [3, 6, 9, 2, 10, 8, 7, 5, 1, 4]
LabVIEW
Lambdatalk
<lang Scheme> {def shuffle
{def shuffle.in
{lambda {:a}
{S.map {{lambda {:a :i}
{A.swap :i
{floor {* {random} {+ :i 1}}} // j = random integer from 0 to i+1
:a}} :a}
{S.serie {- {A.length :a} 1} 0 -1}}}} // from length-1 to 0
{lambda {:a}
{let { {:b {A.duplicate :a}} } // optionnaly prevents modifying the original array
{S.replace \s by in {shuffle.in :b} // trim extra spaces
:b}}}} // return the new array
-> shuffle
{def A.swap // should probably be promoted as a primitive
{lambda {:i :j :a}
{let { {:i :i}
{:gja {A.get :j :a}}
{:b {A.set! :j {A.get :i :a} :a}}
} {let { {_ {A.set! :i :gja :b} }}}}}} // side effect without any return value
-> A.swap
{def B {A.new a b c d e f g h i j k l m n o p q r s t u v w x y z}} -> B
{shuffle {B}} -> [z,t,q,w,c,n,a,u,r,y,i,s,f,d,g,m,h,x,b,e,k,p,l,o,j,v] </lang>
Lasso
<lang lasso>define staticarray->swap(p1::integer,p2::integer) => {
fail_if(
#p1 < 1 or #p2 < 1 or
#p1 > .size or #p2 > .size,
'invalid parameters'
)
#p1 == #p2
? return
local(tmp) = .get(#p2) .get(#p2) = .get(#p1) .get(#p1) = #tmp
} define staticarray->knuthShuffle => {
loop(-from=.size, -to=2, -by=-1) => {
.swap(math_random(1, loop_count), loop_count)
}
}
(1 to 10)->asStaticArray->knuthShuffle&asString</lang>
- Output:
staticarray(9, 5, 6, 1, 10, 8, 3, 4, 2, 7)
Liberty BASIC
<lang lb>'Declared the UpperBound to prevent confusion with lots of 9's floating around.... UpperBound = 9 Dim array(UpperBound)
For i = 0 To UpperBound
array(i) = Int(Rnd(1) * 10) Print array(i)
Next i
For i = 0 To UpperBound
'set a random value because we will need to use the same value twice randval = Int(Rnd(1) * (UpperBound - i)) temp1 = array(randval) temp2 = array((UpperBound - i)) array(randval) = temp2 array((UpperBound - i)) = temp1
Next i
Print For i = 0 To UpperBound
Print array(i)
Next i</lang>
Logo
<lang logo>to swap :i :j :a
localmake "t item :i :a setitem :i :a item :j :a setitem :j :a :t
end to shuffle :a
for [i [count :a] 2] [swap 1 + random :i :i :a]
end
make "a {1 2 3 4 5 6 7 8 9 10} shuffle :a show :a</lang> Lhogho does not have a setitem, and also does things more 'function'ally. <lang logo>to slice :lst :start :finish local "res make "res [] for "i [:start :finish 1] [ make "j item :i :lst make "res se :res :j ] op :res end
to setitem :n :lst :val local "lhs local "rhs make "lhs slice :lst 1 :n-1 make "rhs slice :lst :n+1 count :lst op (se :lhs :val :rhs) end
to swap :i :j :a local "t make "t item :i :a make "a setitem :i :a item :j :a make "a setitem :j :a :t op :a end
to shuffle :a for "i [count :a 2] [ make "a swap 1 + random :i :i :a ] op :a end
make "a ( list 1 2 3 4 5 6 7 8 9 10 ) make "a shuffle :a show :a</lang>
Lua
<lang lua>function table.shuffle(t)
for n = #t, 1, -1 do local k = math.random(n) t[n], t[k] = t[k], t[n] end return t
end
math.randomseed( os.time() ) a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} table.shuffle(a) for i,v in ipairs(a) do print(i,v) end</lang>
M2000 Interpreter
<lang M2000 Interpreter> Dim Base 0, A(3) For k=1 to 6 {
A(0):=10,20, 30
For i=len(A())-1 to 0 {
let j=random(0,i)
Swap a(i), a(j)
}
Print A()
}
</lang>
M4
<lang M4>divert(-1) define(`randSeed',141592653) define(`rand_t',`eval(randSeed^(randSeed>>13))') define(`random',
`define(`randSeed',eval((rand_t^(rand_t<<18))&0x7fffffff))randSeed')
define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`set',`define(`$1[$2]',`$3')') define(`get',`defn($1[$2])') define(`new',`set($1,size,0)') define(`deck',
`new($1)for(`x',1,$2,
`set(`$1',x,x)')`'set(`$1',size,$2)')
define(`show',
`for(`x',1,get($1,size),`get($1,x)`'ifelse(x,get($1,size),`',`, ')')')
define(`swap',`set($1,$2,get($1,$4))`'set($1,$4,$3)') define(`shuffle',
`define(`s',get($1,size))`'for(`x',1,decr(s),
`swap($1,x,get($1,x),eval(x+random%(s-x+1)))')')
divert
deck(`b',52) show(`b') shuffle(`b') show(`b')</lang>
- Output:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 6, 22, 33, 51, 35, 45, 16, 32, 7, 34, 10, 44, 5, 38, 43, 25, 29, 9, 37, 20, 21, 48, 24, 46, 8, 26, 41, 47, 49, 36, 14, 31, 15, 39, 12, 17, 13, 1, 3, 4, 27, 11, 28, 2, 19, 30, 42, 50, 18, 52, 40, 23
Mathematica/Wolfram Language
Usage of built-in function: <lang Mathematica>RandomSample[{1, 2, 3, 4, 5, 6}]</lang> Custom function: <lang Mathematica>Shuffle[input_List /; Length[input] >= 1] :=
Module[{indices = {}, allindices = Range[Length[input]]},
Do[
AppendTo[indices,
Complement[allindices, indices][[RandomInteger[{1, i}]]]];
,
{i, Length[input], 1, -1}
];
inputindices
]</lang>
Example: <lang Mathematica>Shuffle[{1, 2, 3, 4, 5, 6}]</lang>
MATLAB
Because this shuffle is done using rounds of operations on subsets of decreasing size, this is not an algorithm that can be vectorized using built-in MATLAB functions. So, we have to go old-school, no fancy MATLAB trickery. <lang MATLAB>function list = knuthShuffle(list)
for i = (numel(list):-1:2)
j = floor(i*rand(1) + 1); %Generate random int between 1 and i
%Swap element i with element j.
list([j i]) = list([i j]);
end
end</lang> There is an alternate way to do this that is not a true Knuth Shuffle, but operates with the same spirit. This alternate version produces the same output, saves some space, and can be implemented in-line without the need to encapsulate it in a function call like the Knuth Shuffle. <lang MATLAB>function list = randSort(list)
list = list( randperm(numel(list)) );
end</lang>
Maxima
<lang maxima>/* Maxima has an implementation of Knuth shuffle */ random_permutation([a, b, c]);</lang>
Modula-3
<lang modula3>MODULE Shuffle EXPORTS Main;
IMPORT IO, Fmt, Random;
VAR a := ARRAY [0..9] OF INTEGER {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
VAR temp: INTEGER;
n: INTEGER := NUMBER(a);
BEGIN
WITH rand = NEW(Random.Default).init() DO
WHILE n > 1 DO
WITH k = rand.integer(0, n - 1) DO
DEC(n);
temp := a[n];
a[n] := a[k];
a[k] := temp;
END;
END;
END;
END Shuffle;
BEGIN
Shuffle(a);
FOR i := FIRST(a) TO LAST(a) DO
IO.Put(Fmt.Int(a[i]) & " ");
END;
IO.Put("\n");
END Shuffle.</lang>
- Output:
martin@thinkpad:~$ ./shuffle 9 2 7 3 6 8 4 5 1 10 martin@thinkpad:~$ ./shuffle 1 7 8 10 5 4 6 3 9 2
MUMPS
<lang MUMPS>Shuffle(items,separator) New ii,item,list,n Set list="",n=0 Set ii="" For Set ii=$Order(items(ii)) Quit:ii="" Do . Set n=n+1,list(n)=items(ii),list=list_$Char(n) . Quit For Quit:list="" Do . Set n=$Random($Length(list))+1 . Set item=list($ASCII(list,n)) . Set $Extract(list,n)="" . Write item,separator . Quit Quit CardDeck New card,ii,suite Set ii=0 For suite="Spades","Hearts","Clubs","Diamonds" Do . For card=2:1:10,"Jack","Queen","King","Ace" Do . . Set ii=ii+1,items(ii)=card_" of "_suite . . Quit . Quit Quit
Kill items Set items(91)="Red" Set items(82)="White" Set items(73)="Blue" Set items(64)="Yellow" Set items(55)="Green" Do Shuffle(.items," ") ; Red Yellow White Green Blue Do Shuffle(.items," ") ; Red Blue Yellow White Green Do Shuffle(.items," ") ; Green Blue Yellow White Red
Kill items Do CardDeck,Shuffle(.items,$Char(13,10)) Queen of Hearts 9 of Diamonds 10 of Hearts King of Hearts 7 of Diamonds 9 of Clubs 6 of Diamonds 8 of Diamonds Jack of Spades Ace of Hearts Queen of Diamonds 9 of Hearts 2 of Hearts King of Clubs 10 of Spades 7 of Clubs 6 of Clubs 3 of Diamonds 3 of Spades Queen of Clubs Ace of Spades 4 of Hearts Ace of Diamonds 7 of Spades Ace of Clubs King of Spades 10 of Diamonds Jack of Diamonds 8 of Clubs 4 of Spades Jack of Hearts 10 of Clubs 4 of Diamonds 3 of Hearts 2 of Diamonds 5 of Hearts Jack of Clubs 2 of Clubs 5 of Diamonds 6 of Hearts 4 of Clubs 9 of Spades 3 of Clubs 5 of Spades 6 of Spades 7 of Hearts 8 of Spades 8 of Hearts 2 of Spades Queen of Spades King of Diamonds 5 of Clubs</lang>
Nemerle
<lang Nemerle>Shuffle[T] (arr : array[T]) : array[T] {
def rnd = Random();
foreach (i in [0 .. (arr.Length - 2)])
arr[i] <-> arr[(rnd.Next(i, arr.Length))];
arr
}</lang>
NetRexx
version 1
<lang NetRexx>/* NetRexx */ options replace format comments java crossref savelog symbols nobinary
import java.util.List
cards = [String -
'hA', 'h2', 'h3', 'h4', 'h5', 'h6', 'h7', 'h8', 'h9', 'h10', 'hJ', 'hQ', 'hK' - , 'cA', 'c2', 'c3', 'c4', 'c5', 'c6', 'c7', 'c8', 'c9', 'c10', 'cJ', 'cQ', 'cK' - , 'dA', 'd2', 'd3', 'd4', 'd5', 'd6', 'd7', 'd8', 'd9', 'd10', 'dJ', 'dQ', 'dK' - , 'sA', 's2', 's3', 's4', 's5', 's6', 's7', 's8', 's9', 's10', 'sJ', 'sQ', 'sK' -
] cardsLen = cards.length deck = ArrayList(cardsLen) loop c_ = 0 to cardsLen - 1
deck.add(String(cards[c_])) end c_
showHand(deck) deck = ArrayList shuffle(deck) showHand(deck)
return
method shuffle(deck = List) public static binary returns List
rn = Random() dl = deck.size
loop i_ = dl - 1 to 1 by -1 j_ = rn.nextInt(i_) __ = deck.get(i_) deck.set(i_, deck.get(j_)) deck.set(j_, __) end i_
return deck
method showHand(deck = ArrayList) public static binary
dl = deck.size hl = dl % 4 loop c_ = 0 to dl - 1 by hl d_ = c_ + hl if d_ >= dl then d_ = dl say ArrayList(deck.subList(c_, d_)).toString end c_ say
return</lang>
- Output:
[hA, h2, h3, h4, h5, h6, h7, h8, h9, h10, hJ, hQ, hK] [cA, c2, c3, c4, c5, c6, c7, c8, c9, c10, cJ, cQ, cK] [dA, d2, d3, d4, d5, d6, d7, d8, d9, d10, dJ, dQ, dK] [sA, s2, s3, s4, s5, s6, s7, s8, s9, s10, sJ, sQ, sK] [s8, c10, sJ, c8, h10, h3, s3, d6, hJ, d3, c7, h5, s5] [h8, d10, cK, s6, dQ, d9, d4, c4, c6, h6, cA, sA, dK] [dJ, dA, d7, c2, d2, s10, sK, h2, c5, s7, cJ, d5, h9] [c9, d8, c3, s9, cQ, sQ, h4, s4, hQ, h7, hK, hA, s2]
version 2
<lang NetRexx>/* NetRexx ------------------------------------------------------------
- 08.01.2014 Walter Pachl modified to show state development a la Rexx
- --------------------------------------------------------------------*/
options replace format comments java crossref savelog symbols nobinary
import java.util.List
cards = [String '1','2','3','4','5','6','7','8','9','10'] cardsLen = cards.length deck = ArrayList(cardsLen) loop c_ = 0 to cardsLen - 1
deck.add(String(cards[c_])) end c_
showHand(deck,'In ') deck = ArrayList shuffle(deck) showHand(deck,'Out') return
method shuffle(deck = List) public static binary returns List
rn = Random() dl = deck.size loop i_ = dl - 1 to 1 by -1 j_ = rn.nextInt(i_) __ = deck.get(i_) deck.set(i_, deck.get(j_)) deck.set(j_, __) say i_ j_ ArrayList(deck.subList(0,i_+1)).toString end i_ return deck
method showHand(deck = ArrayList,tag=REXX) public static binary
say tag ArrayList(deck.subList(0,deck.size)).toString return</lang>
- Output:
In [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 9 5 [1, 2, 3, 4, 5, 10, 7, 8, 9, 6] 8 4 [1, 2, 3, 4, 9, 10, 7, 8, 5] 7 2 [1, 2, 8, 4, 9, 10, 7, 3] 6 0 [7, 2, 8, 4, 9, 10, 1] 5 4 [7, 2, 8, 4, 10, 9] 4 1 [7, 10, 8, 4, 2] 3 2 [7, 10, 4, 8] 2 0 [4, 10, 7] 1 0 [10, 4] Out [10, 4, 7, 8, 2, 9, 1, 3, 5, 6]
Nim
Note that the function "shuffle" exists in the standard module "random" and that it uses the Knuth shuffle. <lang nim>import random randomize()
proc shuffle[T](x: var openArray[T]) =
for i in countdown(x.high, 1): let j = rand(i) swap(x[i], x[j])
var x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] shuffle(x) echo x</lang>
Objective-C
<lang objc>#import <Foundation/Foundation.h>
@interface NSMutableArray (KnuthShuffle) - (void)knuthShuffle; @end @implementation NSMutableArray (KnuthShuffle) - (void)knuthShuffle {
for (NSUInteger i = self.count-1; i > 0; i--) {
NSUInteger j = arc4random_uniform(i+1);
[self exchangeObjectAtIndex:i withObjectAtIndex:j];
}
} @end
int main() {
@autoreleasepool {
NSMutableArray *x = [NSMutableArray arrayWithObjects:@0, @1, @2, @3, @4, @5, @6, @7, @8, @9, nil];
[x knuthShuffle];
NSLog(@"%@", x);
}
return 0;
}</lang>
- Output:
(
9,
4,
0,
8,
5,
3,
2,
1,
7,
6
)
OCaml
<lang ocaml>let shuffle arr =
for n = Array.length arr - 1 downto 1 do let k = Random.int (n + 1) in let temp = arr.(n) in arr.(n) <- arr.(k); arr.(k) <- temp done</lang>
Oforth
Works with any object that has the property to be Indexable (Lists, Intervals, ...) Returns a new list
<lang Oforth>Indexable method: shuffle | s i l |
self asListBuffer ->l self size dup ->s 1- loop: i [ s i - rand i + i l swapValues ] l dup freeze ; </lang>
Ol
There are two functions - one for tuples (that speedy) and second for lists (that uses previous one).
Ol is functional language, so we should make a copy of shuffling tuple and return this shuffled copy.
<lang scheme> (define (shuffle tp)
(let ((items (vm:cast tp (type tp)))) ; make a copy
(for-each (lambda (i)
(let ((a (ref items i))
(j (+ 1 (rand! i))))
(set-ref! items i (ref items j))
(set-ref! items j a)))
(reverse (iota (size items) 1)))
items))
(define (list-shuffle tp)
(map (lambda (i)
(list-ref tp i))
(tuple->list
(shuffle (list->tuple (iota (length tp)))))))
</lang>
Testing: <lang scheme> (define items (tuple 1 2 3 4 5 6 7 8 9)) (print "tuple before: " items) (print "tuple after: " (shuffle items))
(define items (list 1 2 3 4 5 6 7 8 9)) (print "list before: " items) (print "list after: " (list-shuffle items)) </lang> Output:
tuple before: #[1 2 3 4 5 6 7 8 9] tuple after: #[9 4 1 3 7 2 5 6 8] list before: (1 2 3 4 5 6 7 8 9) list after: (8 2 4 9 5 3 6 1 7)
Oz
<lang oz>declare
proc {Shuffle Arr}
Low = {Array.low Arr}
High = {Array.high Arr}
in
for I in High..Low;~1 do
J = Low + {OS.rand} mod (I - Low + 1)
OldI = Arr.I
in
Arr.I := Arr.J
Arr.J := OldI
end
end
X = {Tuple.toArray unit(0 1 2 3 4 5 6 7 8 9)}
in
{Show {Array.toRecord unit X}}
{Shuffle X}
{Show {Array.toRecord unit X}}</lang>
PARI/GP
<lang parigp>FY(v)={
forstep(n=#v,2,-1, my(i=random(n)+1,t=v[i]); v[i]=v[n]; v[n]=t ); v
};
FY(vector(52,i,i))</lang>
Pascal
<lang Pascal>program Knuth;
const
startIdx = -5; max = 11;
type
tmyData = string[9]; tmylist = array [startIdx..startIdx+max-1] of tmyData;
procedure InitList(var a: tmylist); var
i: integer;
Begin
for i := Low(a) to High(a) do str(i:3,a[i])
end;
procedure shuffleList(var a: tmylist); var
i,k : integer; tmp: tmyData;
begin
for i := High(a)-low(a) downto 1 do begin k := random(i+1) + low(a); tmp := a[i+low(a)]; a[i+low(a)] := a[k]; a[k] := tmp end
end;
procedure DisplayList(const a: tmylist); var
i : integer;
Begin
for i := Low(a) to High(a) do write(a[i]); writeln
end;
{ Test and display } var
a: tmylist; i: integer;
begin
randomize; InitList(a); DisplayList(a); writeln; For i := 0 to 4 do Begin shuffleList(a); DisplayList(a); end;
end.</lang>
- Output:
-5 -4 -3 -2 -1 0 1 2 3 4 5 -5 4 0 -4 3 -1 -3 1 -2 5 2 2 0 1 -5 -1 5 -3 4 -2 3 -4 3 -1 -2 5 -4 1 2 -5 -3 4 0 -4 1 -1 -5 5 2 0 3 -2 -3 4 -3 -5 4 2 -4 0 5 3 1 -1 -2
Perl
<lang perl>sub shuffle {
my @a = @_;
foreach my $n (1 .. $#a) {
my $k = int rand $n + 1;
$k == $n or @a[$k, $n] = @a[$n, $k];
}
return @a;
}</lang>
Phix
sequence cards = tagset(52) puts(1,"Before: ") ?cards for i=52 to 1 by -1 do integer r = rand(i) {cards[r],cards[i]} = {cards[i],cards[r]} end for puts(1,"After: ") ?cards puts(1,"Sorted: ") ?sort(cards)
- Output:
Before: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
After: {42,4,48,28,11,3,52,51,22,2,49,38,25,33,27,35,18,44,5,7,21,13,36,29,43,6,9,31,10,30,20,16,46,34,8,17,14,45,37,24,32,41,50,15,39,40,47,23,1,12,26,19}
Sorted: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
PHP
<lang php>//The Fisher-Yates original Method function yates_shuffle($arr){ $shuffled = Array(); while($arr){ $rnd = array_rand($arr); $shuffled[] = $arr[$rnd]; array_splice($arr, $rnd, 1); } return $shuffled; }
//The modern Durstenfeld-Knuth algorithm function knuth_shuffle(&$arr){ for($i=count($arr)-1;$i>0;$i--){ $rnd = mt_rand(0,$i); list($arr[$i], $arr[$rnd]) = array($arr[$rnd], $arr[$i]); } }</lang>
PicoLisp
<lang PicoLisp>(seed (in "/dev/urandom" (rd 8)))
(de knuth (Lst)
(for (N (length Lst) (>= N 2) (dec N))
(let I (rand 1 N)
(xchg (nth Lst N) (nth Lst I)) ) ) )
(let L (range 1 15)
(println 'before L) (knuth L) (println 'after L) )</lang>
- Output:
before (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) after (12 15 4 13 11 9 7 1 2 14 5 6 8 3 10)
PL/I
version 1
<lang pli>declare T(0:10) fixed binary initial (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11); declare (i, j, temp) fixed binary; do i = lbound(T,1) to hbound(T,1);
j = min(random() * 12, 11); temp = T(j); T(j) = T(i); T(i) = temp;
end;</lang>
version 2
<lang pli> kn: Proc Options(main);
/*--------------------------------------------------------------------
* 07.01.2014 Walter Pachl translated from REXX version 2
* Iteration i: only the first i elements are candidates for swapping
*-------------------------------------------------------------------*/
Dcl T(10) Bin Fixed(15) Init(1,2,3,4,5,6,7,8,9,10);
Dcl (i,j,temp) Bin Fixed(15) init(0);
Dcl h Char(6);
Call show('In',10); /* show start */
do i = 10 To 2 By -1; /* shuffle */
j=random()*i+1;
Put string(h)Edit(i,j)(f(2),f(3));
temp=t(i); t(i)=t(j); t(j)=temp; /* t(i) <-> t(j) */
Call show(h,i); /* show intermediate states */
end;
Call show('Out',10); /* show final state */
show: Proc(txt,n); Dcl txt Char(*); Dcl n Bin Fixed(15); Put Edit(txt,(t(k) do k=1 To n))(Skip,a(7),10(f(3))); End; end;</lang>
- Output:
In 1 2 3 4 5 6 7 8 9 10 10 5 1 2 3 4 10 6 7 8 9 5 9 1 9 2 3 4 10 6 7 8 1 8 7 9 2 3 4 10 6 8 7 7 2 9 8 3 4 10 6 2 6 6 9 8 3 4 10 6 5 3 9 8 10 4 3 4 2 9 4 10 8 3 3 9 4 10 2 1 4 9 Out 4 9 10 8 3 6 2 7 1 5
PowerShell
<lang powershell>$A = 1, 2, 3, 4, 5 Get-Random $A -Count $A.Count</lang>
<lang powershell>function shuffle ($a) {
$c = $a.Clone() # make copy to avoid clobbering $a
1..($c.Length - 1) | ForEach-Object {
$i = Get-Random -Minimum $_ -Maximum $c.Length
$c[$_-1],$c[$i] = $c[$i],$c[$_-1]
$c[$_-1] # return newly-shuffled value
}
$c[-1] # last value
}</lang> This yields the values one by one instead of returning the array as a whole, so the rest of the pipeline can work on the values while shuffling is still in progress.
PureBasic
<lang PureBasic>EnableExplicit
Procedure KnuthShuffle(Array a(1))
Protected i, last = ArraySize(a())
For i = last To 1 Step -1
Swap a(i), a(Random(i))
Next
EndProcedure
Procedure.s ArrayToString(Array a(1))
Protected ret$, i, last = ArraySize(a())
ret$ = Str(a(0))
For i = 1 To last
ret$ + "," + Str(a(i))
Next
ProcedureReturn ret$
EndProcedure
- NumElements = 10
Dim a(#NumElements-1) Define i
For i = 0 To #NumElements-1
a(i) = i
Next
KnuthShuffle(a()) Debug "shuffled: " + ArrayToString(a())</lang>
- Output:
shuffled: 1,8,6,0,5,9,2,4,7,3
Python
Python's standard library function random.shuffle uses this algorithm and so should normally be used.
The function below is very similar:
<lang python>from random import randrange
def knuth_shuffle(x):
for i in range(len(x)-1, 0, -1):
j = randrange(i + 1)
x[i], x[j] = x[j], x[i]
x = list(range(10)) knuth_shuffle(x) print("shuffled:", x)</lang>
- Output:
shuffled: [5, 1, 6, 0, 8, 4, 2, 3, 9, 7]
We could also write our own Knuth shuffle function as a fold, with a non-mutating swap function:
<lang python>Knuth shuffle as a fold
from functools import reduce from random import randint
- knuthShuffle :: [a] -> IO [a]
def knuthShuffle(xs):
A pseudo-random shuffle of the elements in xs.
return reduce(
swapped,
enumerate(randoms(len(xs))), xs
)
- swapped :: (Int, Int) -> [a] -> [a]
def swapped(xs, ij):
New list in which the elements at indices
i and j of xs are swapped.
def go(a, b):
if a != b:
m, n = (a, b) if b > a else (b, a)
l, ht = splitAt(m)(xs)
ys, zs = splitAt((n - m) - 1)(ht[1:])
return l + [zs[0]] + ys + [ht[0]] + zs[1:]
else:
return xs
i, j = ij
z = len(xs) - 1
return xs if i > z or j > z else go(i, j)
- randoms :: Int -> IO [Int]
def randoms(n):
Pseudo-random list of n - 1 indices. return list(map(randomRInt(0)(n - 1), range(1, n)))
- TEST ----------------------------------------------------
- main :: IO ()
def main():
Repeated Knuth shuffles of ['a' .. 'k']
print(
fTable(main.__doc__ + ':\n')(str)(lambda x: .join(x))(
lambda _: knuthShuffle(list('abcdefghijk'))
)(range(1, 11))
)
- GENERIC -------------------------------------------------
- randomRInt :: Int -> Int -> IO () -> Int
def randomRInt(m):
The return value of randomRInt is itself
a function. The returned function, whenever
called, yields a a new pseudo-random integer
in the range [m..n].
return lambda n: lambda _: randint(m, n)
- splitAt :: Int -> [a] -> ([a], [a])
def splitAt(n):
A tuple pairing the prefix of length n
with the rest of xs.
return lambda xs: (xs[0:n], xs[n:])
- FORMATTING -----------------------------------------------------------
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
Repeated Knuth shuffles of ['a' .. 'k']: 1 -> kdafbhigejc 2 -> jhdkgeicabf 3 -> aciebghdfkj 4 -> fjahegibckd 5 -> cabejfidkgh 6 -> gbecahfkijd 7 -> jegchkdifba 8 -> fcjkghiadeb 9 -> ihfebdajgkc 10 -> hjkigbadcfe
Quackery
The word shuffle is predefined in Quackery (and shown below) - it shuffles a nest (an immutable dynamic array) by removing random items from the nest (i.e. creating a new array with that item removed) and appending them to an (initially empty) nest (i.e. creating a new array with that item appended). It fits the criteria for this task with the relaxations noted at the end of the task description.
The word knuffle is probably an entirely in-place shuffle, if the dynamic memory allocation routines for a particular implementation of Quackery allow in-place modification of a dynamic array when there is only a single pointer to the array. (After the first invocation of poke inside [exch] there will definitely only be a single pointer to the array.)
<lang Quackery> [ [] swap dup size times
[ dup size random pluck
nested rot join swap ]
drop ] is shuffle ( [ --> [ )
[ temp put
2dup swap
temp share swap peek
temp share rot peek
dip
[ swap
temp take
swap poke
temp put ]
swap
temp take
swap poke ] is [exch] ( n n [ --> [ )
[ dup size 1 - times
[ i 1+ dup 1+ random
rot [exch] ] ] is knuffle ( [ --> [ )</lang>
- Output:
Testing in the Quackery shell (REPL).
/O> ' [ 10 11 12 13 14 15 16 17 18 19 ] ... 10 times [ knuffle dup echo cr ] ... [ 14 19 11 13 18 17 10 16 12 15 ] [ 10 15 18 17 13 14 12 16 11 19 ] [ 19 11 10 14 15 16 12 18 17 13 ] [ 14 13 19 15 10 16 11 17 18 12 ] [ 18 13 11 15 17 16 12 10 14 19 ] [ 18 17 10 13 12 19 15 16 14 11 ] [ 10 19 17 12 13 14 15 16 18 11 ] [ 10 16 17 18 13 11 15 19 12 14 ] [ 18 19 17 11 10 14 16 12 13 15 ] [ 19 11 10 14 16 12 17 18 15 13 ] Stack: [ 10 15 13 14 12 19 16 11 17 18 ] /O> 10 times [ shuffle dup echo cr ] ... [ 10 13 11 14 18 15 12 17 16 19 ] [ 12 19 16 17 10 13 14 11 18 15 ] [ 11 14 12 17 15 19 13 16 18 10 ] [ 17 15 14 18 16 19 11 10 13 12 ] [ 14 15 18 13 10 16 17 12 19 11 ] [ 12 14 11 16 15 10 19 18 17 13 ] [ 14 12 15 18 16 19 11 10 13 17 ] [ 18 19 15 16 14 12 13 11 17 10 ] [ 14 18 19 11 16 12 13 15 17 10 ] [ 17 19 11 18 14 10 12 13 16 15 ] Stack: [ 17 19 11 18 14 10 12 13 16 15 ]
R
See also, the built-in function 'sample'.
Original Fisher-Yates version
<lang rsplus>fisheryatesshuffle <- function(n) {
pool <- seq_len(n)
a <- c()
while(length(pool) > 0)
{
k <- sample.int(length(pool), 1)
a <- c(a, pool[k])
pool <- pool[-k]
}
a
}</lang>
Knuth variation
<lang rsplus>fisheryatesknuthshuffle <- function(n) {
a <- seq_len(n)
while(n >=2)
{
k <- sample.int(n, 1)
if(k != n)
{
temp <- a[k]
a[k] <- a[n]
a[n] <- temp
}
n <- n - 1
}
a
}
- Example usage:
fisheryatesshuffle(6) # e.g. 1 3 6 2 4 5 x <- c("foo", "bar", "baz", "quux") x[fisheryatesknuthshuffle(4)] # e.g. "bar" "baz" "quux" "foo"</lang>
Short version
After accounting for R being 1-indexed rather than 0-indexed, it's not hard to implement the pseudo-code given in the task almost exactly: <lang rsplus>knuth <- function(vec) {
last <- length(vec)
if(last >= 2)
{
for(i in last:2)
{
j <- sample(seq_len(i), size = 1)
vec[c(i, j)] <- vec[c(j, i)]
}
}
vec
}
- Demonstration:
knuth(integer(0)) knuth(c(10)) replicate(10, knuth(c(10, 20))) replicate(10, knuth(c(10, 20, 30))) knuth(c("Also", "works", "for", "strings"))</lang>
- Output:
> knuth(integer(0))
integer(0)
> knuth(c(10))
[1] 10
> replicate(10, knuth(c(10, 20)))
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 20 20 10 10 20 10 20 10 20 10
[2,] 10 10 20 20 10 20 10 20 10 20
> replicate(10, knuth(c(10, 20, 30)))
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 30 10 20 20 30 30 10 30 10 10
[2,] 10 20 30 10 10 10 20 20 20 20
[3,] 20 30 10 30 20 20 30 10 30 30
> knuth(c("Also", "works", "for", "strings"))
[1] "strings" "Also" "for" "works"
Racket
<lang scheme>#lang racket
(define (swap! vec i j)
(let ([tmp (vector-ref vec i)]) (vector-set! vec i (vector-ref vec j)) (vector-set! vec j tmp)))
(define (knuth-shuffle x)
(if (list? x)
(vector->list (knuth-shuffle (list->vector x)))
(begin (for ([i (in-range (sub1 (vector-length x)) 0 -1)])
(define r (random (+ i 1)))
(swap! x i r))
x)))
(knuth-shuffle '(1 2 3 4))</lang>
Raku
(formerly Perl 6)
<lang perl6>sub shuffle (@a is copy) {
for 1 ..^ @a -> $n {
my $k = (0 .. $n).pick;
$k == $n or @a[$k, $n] = @a[$n, $k];
}
return @a;
}</lang> The shuffle is also built into the pick method on lists when you pass it a "whatever" for the number to pick: <lang perl6>my @deck = @cards.pick(*);</lang>
REBOL
<lang rebol>REBOL [
Title: "Fisher-Yates"
Purpose: {Fisher-Yates shuffling algorithm}
]
fisher-yates: func [b [block!] /local n i j k] [
n: length? b: copy b
i: n
while [i > 1] [
if i <> j: random i [
error? set/any 'k pick b j
change/only at b j pick b i
change/only at b i get/any 'k
]
i: i - 1
]
b
]</lang>
REXX
version 0, card pips
<lang rexx>/*REXX program shuffles a deck of playing cards (with jokers) using the Knuth shuffle.*/ rank= 'A 2 3 4 5 6 7 8 9 10 J Q K' /*pips of the various playing cards. */ suit= '♣♠♦♥' /*suit " " " " " */ parse arg seed . /*obtain optional argument from the CL.*/ if datatype(seed,'W') then call random ,,seed /*maybe use for RANDOM repeatability.*/ say '══════════════════ getting a new deck out of the box ···' @.1= 'highJoker' /*good decks have a color joker, and a */ @.2= 'lowJoker' /* ··· black & white joker. */ cards=2 /*now, there're 2 cards are in the deck*/
do j =1 for length(suit)
do k=1 for words(rank); cards=cards + 1
@.cards=substr(suit, j, 1)word(rank, k)
end /*k*/
end /*j*/
call show say; say '══════════════════ shuffling' cards "cards ···"
do s=cards by -1 to 2; ?=random(1,s); parse value @.? @.s with @.s @.?
/* [↑] swap two cards in the deck. */
end /*s*/
call show exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ show: _=; do m=1 for cards; _=_ @.m; end /*m*/; say _; return</lang> output
══════════════════ getting a new deck out of the box ··· highJoker lowJoker ♣A ♣2 ♣3 ♣4 ♣5 ♣6 ♣7 ♣8 ♣9 ♣10 ♣J ♣Q ♣K ♠A ♠2 ♠3 ♠4 ♠5 ♠6 ♠7 ♠8 ♠9 ♠10 ♠J ♠Q ♠K ♦A ♦2 ♦3 ♦4 ♦5 ♦6 ♦7 ♦8 ♦9 ♦10 ♦J ♦Q ♦K ♥A ♥2 ♥3 ♥4 ♥5 ♥6 ♥7 ♥8 ♥9 ♥10 ♥J ♥Q ♥K ══════════════════ shuffling 54 cards ··· ♣J ♦3 ♥5 ♣10 ♥2 ♥J ♣6 ♦4 ♠2 ♥8 ♥A ♠A ♣9 ♣5 ♠7 ♦6 ♥6 ♠10 ♥9 ♦2 lowJoker ♥3 ♠5 ♠K ♣K ♣8 ♣Q ♠Q ♣2 ♦8 ♠4 ♣7 ♦5 ♥K ♣A ♠6 ♠J ♦Q ♦7 ♠9 ♦10 ♦K ♣4 ♥7 ♣3 ♠3 highJoker ♦A ♥4 ♦J ♠8 ♦9 ♥Q ♥10
version 1, card names
This version handles items with (leading/trailing/embedded) blanks in them, so parse isn't an option for shuffling. <lang rexx>/*REXX program shuffles a deck of playing cards (with jokers) using the Knuth shuffle.*/ rank = 'ace deuce trey 4 5 6 7 8 9 10 jack queen king' /*use pip names for cards*/ suit = 'club spade diamond heart' /* " suit " " " */ say '══════════════════ getting a new deck out of the box ···' @.1= ' color joker' /*good decks have a color joker, and a */ @.2= ' b&w joker' /* ··· black & white joker. */ cards=2 /*now, there're 2 cards are in the deck*/
do j =1 for words(suit)
do k=1 for words(rank); cards=cards+1 /*bump the card counter. */
@.cards=right(word(suit,j),7) word(rank,k) /*assign a card name. */
end /*k*/
end /*j*/
call show 'ace' /*inserts blank when an ACE is found.*/ say; say '══════════════════ shuffling' cards "cards ···"
do s=cards by -1 to 2; ?=random(1,s); _=@.?; @.?=@.s; @.s=_
end /*s*/ /* [↑] swap two cards in the deck. */
call show exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ show: parse arg break; say /*get separator card, show blank line. */
do m=1 for cards /* [↓] traipse through the card deck. */
if pos(break,@.m)\==0 then say /*show a blank to read cards easier. */
say 'card' right(m, 2) '───►' @.m /*display a particular card from deck. */
end /*m*/
return</lang> output
══════════════════ getting a new deck out of the box ··· card 1 ───► color joker card 2 ───► b&w joker card 3 ───► club ace card 4 ───► club deuce card 5 ───► club trey card 6 ───► club 4 card 7 ───► club 5 card 8 ───► club 6 card 9 ───► club 7 card 10 ───► club 8 card 11 ───► club 9 card 12 ───► club 10 card 13 ───► club jack card 14 ───► club queen card 15 ───► club king card 16 ───► spade ace card 17 ───► spade deuce card 18 ───► spade trey card 19 ───► spade 4 card 20 ───► spade 5 card 21 ───► spade 6 card 22 ───► spade 7 card 23 ───► spade 8 card 24 ───► spade 9 card 25 ───► spade 10 card 26 ───► spade jack card 27 ───► spade queen card 28 ───► spade king card 29 ───► diamond ace card 30 ───► diamond deuce card 31 ───► diamond trey card 32 ───► diamond 4 card 33 ───► diamond 5 card 34 ───► diamond 6 card 35 ───► diamond 7 card 36 ───► diamond 8 card 37 ───► diamond 9 card 38 ───► diamond 10 card 39 ───► diamond jack card 40 ───► diamond queen card 41 ───► diamond king card 42 ───► heart ace card 43 ───► heart deuce card 44 ───► heart trey card 45 ───► heart 4 card 46 ───► heart 5 card 47 ───► heart 6 card 48 ───► heart 7 card 49 ───► heart 8 card 50 ───► heart 9 card 51 ───► heart 10 card 52 ───► heart jack card 53 ───► heart queen card 54 ───► heart king ══════════════════ shuffling 54 cards ··· card 1 ───► spade ace card 2 ───► heart jack card 3 ───► heart ace card 4 ───► diamond 10 card 5 ───► spade 7 card 6 ───► club 10 card 7 ───► club trey card 8 ───► diamond deuce card 9 ───► diamond 7 card 10 ───► spade queen card 11 ───► heart queen card 12 ───► spade deuce card 13 ───► spade 9 card 14 ───► diamond 4 card 15 ───► diamond ace card 16 ───► heart 6 card 17 ───► club king card 18 ───► color joker card 19 ───► spade 6 card 20 ───► heart 5 card 21 ───► diamond 8 card 22 ───► heart 8 card 23 ───► club 7 card 24 ───► heart king card 25 ───► club jack card 26 ───► diamond jack card 27 ───► heart 9 card 28 ───► spade trey card 29 ───► spade jack card 30 ───► spade king card 31 ───► heart 10 card 32 ───► diamond king card 33 ───► diamond trey card 34 ───► heart deuce card 35 ───► heart 4 card 36 ───► diamond 5 card 37 ───► diamond 9 card 38 ───► spade 4 card 39 ───► club 4 card 40 ───► club 5 card 41 ───► spade 5 card 42 ───► club 9 card 43 ───► b&w joker card 44 ───► club 6 card 45 ───► heart 7 card 46 ───► spade 8 card 47 ───► diamond 6 card 48 ───► club deuce card 49 ───► diamond queen card 50 ───► club queen card 51 ───► club ace card 52 ───► heart trey card 53 ───► spade 10 card 54 ───► club 8
version 2
<lang rexx>/* REXX ---------------------------------------------------------------
- 05.01.2014 Walter Pachl
- borrow one improvement from version 1
- 06.01.2014 removed -"- (many tests cost more than few "swaps")
- --------------------------------------------------------------------*/
Call random ,,123456 /* seed for random */ Do i=1 To 10; a.i=i; End; /* fill array */ Call show 'In',10 /* show start */ do i = 10 To 2 By -1 /* shuffle */
j=random(i-1)+1; h=right(i,2) right(j,2) Parse Value a.i a.j With a.j a.i /* a.i <-> a.j */ Call show h,i /* show intermediate states */ end;
Call show 'Out',10 /* show fomaö state */ Exit
show: Procedure Expose a. Parse Arg txt,n ol=left(txt,6); Do k=1 To n; ol=ol right(a.k,2); End Say ol Return</lang>
- Output:
In 1 2 3 4 5 6 7 8 9 10 10 2 1 10 3 4 5 6 7 8 9 2 9 6 1 10 3 4 5 9 7 8 6 8 6 1 10 3 4 5 8 7 9 7 3 1 10 7 4 5 8 3 6 5 1 10 7 4 8 5 5 1 8 10 7 4 1 4 1 4 10 7 8 3 1 7 10 4 2 1 10 7 Out 10 7 4 8 1 5 3 9 6 2
Ring
<lang ring>
- Project : Knuth shuffle
items = list(52) for n = 1 to len(items)
items[n] = n
next knuth(items) showarray(items)
func knuth(items)
for i = len(items) to 1 step -1
j = random(i-1) + 1
if i != j
temp = items[i]
items[i] = items[j]
items[j] = temp
ok
next
func showarray(vect)
see "["
svect = ""
for n = 1 to len(vect)
svect = svect + vect[n] + " "
next
svect = left(svect, len(svect) - 1)
see svect
see "]" + nl
</lang>
[15 1 51 20 45 29 43 8 13 3 41 35 11 7 37 9 38 17 32 48 40 25 44 18 14 50 42 34 2 21 12 4 26 19 23 24 28 46 36 10 5 16 6 49 22 33 39 47 31 52 30 27]
Ruby
<lang ruby>class Array
def knuth_shuffle!
j = length
i = 0
while j > 1
r = i + rand(j)
self[i], self[r] = self[r], self[i]
i += 1
j -= 1
end
self
end
end
r = Hash.new(0) 100_000.times do |i|
a = [1,2,3].knuth_shuffle! r[a] += 1
end
r.keys.sort.each {|a| puts "#{a.inspect} => #{r[a]}"}</lang> results in
[1, 2, 3] => 16572 [1, 3, 2] => 16610 [2, 1, 3] => 16633 [2, 3, 1] => 16714 [3, 1, 2] => 16838 [3, 2, 1] => 16633
More idiomatic: <lang ruby>class Array
def knuth_shuffle!
(length - 1).downto(1) do |i|
j = rand(i + 1)
self[i], self[j] = self[j], self[i]
end
self
end
end</lang>
Run BASIC
<lang runbasic>dim cards(52) for i = 1 to 52 ' make deck
cards(i) = i
next
for i = 52 to 1 step -1 ' shuffle deck
r = int((rnd(1)*i) + 1)
if r <> i then
hold = cards(r)
cards(r) = cards(i)
cards(i) = hold
end if
next
print "== Shuffled Cards ==" ' print shuffled cards for i = 1 to 52
print cards(i);" "; if i mod 18 = 0 then print
next print</lang>
Rust
<lang rust>use rand::Rng;
extern crate rand;
fn knuth_shuffle<T>(v: &mut [T]) {
let mut rng = rand::thread_rng(); let l = v.len();
for n in 0..l {
let i = rng.gen_range(0, l - n);
v.swap(i, l - n - 1);
}
}
fn main() {
let mut v: Vec<_> = (0..10).collect();
println!("before: {:?}", v);
knuth_shuffle(&mut v);
println!("after: {:?}", v);
}</lang>
Scala
<lang Scala>def shuffle[T](a: Array[T]) = {
for (i <- 1 until a.size reverse) {
val j = util.Random nextInt (i + 1)
val t = a(i)
a(i) = a(j)
a(j) = t
}
a
}</lang>
Scheme
A functional version, using lists (inefficient), somewhat unusual in reversing the entire initial sublist on each pass instead of just swapping: <lang Scheme>#!r6rs (import (rnrs base (6))
(srfi :27 random-bits))
(define (semireverse li n)
(define (continue front back n)
(cond
((null? back) front)
((zero? n) (cons (car back) (append front (cdr back))))
(else (continue (cons (car back) front) (cdr back) (- n 1)))))
(continue '() li n))
(define (shuffle li)
(if (null? li)
()
(let
((li-prime (semireverse li (random-integer (length li)))))
(cons (car li-prime) (shuffle (cdr li-prime))))))</lang>
A mutable version, using vectors (efficient): <lang Scheme>#!r6rs (import (rnrs base (6))
(srfi :27 random-bits))
(define (vector-swap! vec i j)
(let
((temp (vector-ref vec i)))
(vector-set! vec i (vector-ref vec j))
(vector-set! vec j temp)))
(define (countdown n)
(if (zero? n)
()
(cons n (countdown (- n 1)))))
(define (vector-shuffle! vec)
(for-each
(lambda (i)
(let
((j (random-integer i)))
(vector-swap! vec (- i 1) j)))
(countdown (vector-length vec))))</lang>
Scratch
See Knuth's shuffle in action. Visit this Scratch implementation to see a demo and inspect its source.
Seed7
<lang seed7>$ include "seed7_05.s7i";
const type: intArray is array integer;
const proc: shuffle (inout intArray: a) is func
local
var integer: i is 0;
var integer: k is 0;
var integer: tmp is 0;
begin
for i range maxIdx(a) downto 2 do
k := rand(1, i);
tmp := a[i];
a[i] := a[k];
a[k] := tmp;
end for;
end func;
const proc: main is func
local
var intArray: a is 10 times 0;
var integer: i is 0;
begin
for key i range a do
a[i] := i;
end for;
shuffle(a);
for i range a do
write(i <& " ");
end for;
writeln;
end func;</lang>
- Output:
7 5 6 8 3 10 9 4 2 1
SenseTalk
<lang sensetalk>set list to 1..9 -- a range, will become a list as needed set last to the number of items in list
repeat with i = last down to 2 -- in SenseTalk, the first index in a list is 1 set j = random (1,i-1) set [item i of list, item j of list] to [item j of list, item i of list] -- swap items end repeat
put list</lang>
- Output:
[8,9,7,3,4,5,1,2,6]
Sidef
<lang ruby>func knuth_shuffle(a) {
for i (a.len ^.. 1) {
var j = i.irand
a[i, j] = a[j, i]
}
return a
}
say knuth_shuffle(@(1..10))</lang>
- Output:
[7, 4, 3, 8, 9, 6, 10, 2, 1, 5]
Smalltalk
<lang smalltalk>"The selector swap:with: is documented, but it seems not
implemented (GNU Smalltalk version 3.0.4); so here it is an implementation"
SequenceableCollection extend [
swap: i with: j [ |t| t := self at: i. self at: i put: (self at: j). self at: j put: t. ]
].
Object subclass: Shuffler [
Shuffler class >> Knuth: aSequenceableCollection [
|n k|
n := aSequenceableCollection size.
[ n > 1 ] whileTrue: [
k := Random between: 1 and: n.
aSequenceableCollection swap: n with: k.
n := n - 1
]
]
].</lang> Testing <lang smalltalk>"Test" |c| c := OrderedCollection new. c addAll: #( 1 2 3 4 5 6 7 8 9 ). Shuffler Knuth: c. c display.</lang>
SNOBOL4
<lang SNOBOL4>* Library for random() -include 'Random.sno'
- # String -> array
define('s2a(str,n)i') :(s2a_end)
s2a s2a = array(n); str = str ' ' sa1 str break(' ') . s2a span(' ') = :s(sa1)f(return) s2a_end
- # Array -> string
define('a2s(a)i') :(a2s_end)
a2s a2s = a2s a ' ' :s(a2s)f(return) a2s_end
- # Knuth shuffle in-place
define('shuffle(a)alen,n,k,tmp') :(shuffle_end)
shuffle n = alen = prototype(a); sh1 k = convert(random() * alen,'integer') + 1
eq(a<n>,a<k>) :s(sh2)
tmp = a<n>; a<n> = a<k>; a<k> = tmp
sh2 n = gt(n,1) n - 1 :s(sh1)
shuffle = a :(return)
shuffle_end
- # Test and display
a = s2a('1 2 3 4 5 6 7 8 9 10',10)
output = a2s(a) '->'
shuffle(a)
output = a2s(a)
end</lang>
- Output:
1 2 3 4 5 6 7 8 9 10 -> 2 10 4 9 1 5 6 8 7 3
Stata
<lang stata>mata function shuffle(a) { n = length(a) r = runiformint(1,1,1,1..n) for (i=n; i>=2; i--) { j = r[i] x = a[i] a[i] = a[j] a[j] = x } return(a) }
shuffle(1..10) end</lang>
Output
1 2 3 4 5 6 7 8 9 10
+---------------------------------------------------+
1 | 8 10 9 1 7 2 6 4 3 5 |
+---------------------------------------------------+Swift
Simple version (any Swift version): Extend Array with shuffle methods; using arc4random_uniform from C stdlib:
<lang swift>import func Darwin.arc4random_uniform
extension Array {
func shuffle() -> Array {
var result = self; result.shuffleInPlace(); return result
}
mutating func shuffleInPlace() {
for i in 1 ..< count { swap(&self[i], &self[Int(arc4random_uniform(UInt32(i+1)))]) }
}
}
// Swift 2.0: print([1, 2, 3, 4, 5, 6, 7, 8, 9, 10].shuffle()) // Swift 1.x: //println([1, 2, 3, 4, 5, 6, 7, 8, 9, 10].shuffle())</lang>
- Output:
[8, 7, 2, 1, 6, 10, 5, 3, 4, 9]
Generic version (any Swift version): While the above code is generic in that it works with arrays of any element type, we can use generic global functions to define shuffling for any mutable collection with random-access index type which is far more generic than the above code:
<lang swift>import func Darwin.arc4random_uniform
func shuffleInPlace<T: MutableCollectionType where T.Index: RandomAccessIndexType>(inout collection: T) {
let i0 = collection.startIndex
for i in i0.successor() ..< collection.endIndex {
let j = i0.advancedBy(numericCast(
arc4random_uniform(numericCast(
i0.distanceTo()
)+1)
))
swap(&collection[i], &collection[j])
}
}
func shuffle<T: MutableCollectionType where T.Index: RandomAccessIndexType>(collection: T) -> T {
var result = collection shuffleInPlace(&result) return result
}
// Swift 2.0: print(shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])) // Swift 1.x: //println(shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))</lang>
- Output:
[2, 5, 7, 1, 6, 10, 4, 3, 8, 9]
While the above solutions work with Swift 2.0 as they are, we can use Swift 2.0's Protocol Oriented Programming features to add shuffling methods to any mutable collection that has a random-access index:
<lang swift>import func Darwin.arc4random_uniform
// Define a protocol for shuffling:
protocol Shufflable {
@warn_unused_result (mutable_variant="shuffleInPlace") func shuffle() -> Self mutating func shuffleInPlace()
}
// Provide a generalized implementation of the shuffling protocol for any mutable collection with random-access index:
extension Shufflable where Self: MutableCollectionType, Self.Index: RandomAccessIndexType {
func shuffle() -> Self {
var result = self
result.shuffleInPlace()
return result
}
mutating func shuffleInPlace() {
let i0 = startIndex
for i in i0+1 ..< endIndex {
let j = i0.advancedBy(numericCast(
arc4random_uniform(numericCast(
i0.distanceTo(i)
)+1)
))
swap(&self[i], &self[j])
}
}
}
// Declare Array's conformance to Shufflable:
extension Array: Shufflable
{ /* Implementation provided by Shufflable protocol extension */ }
print([1, 2, 3, 4, 5, 6, 7, 8, 9, 10].shuffle())</lang>
- Output:
[3, 1, 5, 6, 7, 8, 10, 2, 4, 9]
Tcl
<lang tcl>proc knuth_shuffle lst {
set j [llength $lst]
for {set i 0} {$j > 1} {incr i;incr j -1} {
set r [expr {$i+int(rand()*$j)}]
set t [lindex $lst $i]
lset lst $i [lindex $lst $r]
lset lst $r $t
}
return $lst
}
% knuth_shuffle {1 2 3 4 5} 2 1 3 5 4 % knuth_shuffle {1 2 3 4 5} 5 2 1 4 3 % knuth_shuffle {tom dick harry peter paul mary} tom paul mary harry peter dick</lang> As a test of skewing (an indicator of a poor implementation) this code was used: <lang tcl>% for {set i 0} {$i<100000} {incr i} {
foreach val [knuth_shuffle {1 2 3 4 5}] pos {pos0 pos1 pos2 pos3 pos4} {
incr tots($pos) $val
}
} % parray tots tots(pos0) = 300006 tots(pos1) = 300223 tots(pos2) = 299701 tots(pos3) = 299830 tots(pos4) = 300240</lang>
TI-83 BASIC
Input L1, output L2.
:"SHUFFLE" :L1→L2 :dim(L2)→A :For(B,1,dim(L2)-1) :randInt(1,A)→C :L2(C)→D :L2(A)→L2(C) :D→L2(A) :A-1→A :End :DelVar A :DelVar B :DelVar C :DelVar D :Return
TUSCRIPT
<lang tuscript>$$ MODE TUSCRIPT oldnumbers=newnumbers="",range=20 LOOP nr=1,#range
oldnumbers=APPEND(oldnumbers,nr)
ENDLOOP
PRINT "before ",oldnumbers
LOOP r=#range,1,-1
RANDNR=RANDOM_NUMBERS (1,#r,1) shuffle=SELECT (oldnumbers,#randnr,oldnumbers) newnumbers=APPEND(newnumbers,shuffle)
ENDLOOP
PRINT "after ",newnumbers</lang>
- Output:
before 1'2'3'4'5'6'7'8'9'10'11'12'13'14'15'16'17'18'19'20 after 7'16'13'11'1'9'15'4'18'14'3'12'17'8'19'20'6'5'2'10
uBasic/4tH
<lang>PRINT "before:" FOR L = 0 TO 51
@(L) = L PRINT @(L); " ";
NEXT
FOR L = 51 TO 0 STEP -1
C = RND(L + 1)
IF C # L THEN
PUSH @(C), L, @(L), C
GOSUB 100
ENDIF
NEXT
PRINT : PRINT "after:" FOR L = 0 TO 51
PRINT @(L); " ";
NEXT PRINT END
100 @(POP()) = POP() : @(POP()) = POP() : RETURN</lang>
- Output:
before: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 after: 19 4 49 9 27 35 50 11 2 29 22 48 33 15 17 42 47 28 41 18 34 21 30 39 3 8 23 12 36 26 0 46 7 44 13 14 16 40 10 25 31 32 51 24 20 38 45 6 43 1 5 37
UNIX Shell
<lang bash># Shuffle array[@]. function shuffle { integer i j t
((i = ${#array[@]})) while ((i > 1)); do ((j = RANDOM)) # 0 <= j < 32768 ((j < 32768 % i)) && continue # no modulo bias ((j %= i)) # 0 <= j < i
((i -= 1)) ((t = array[i])) ((array[i] = array[j])) ((array[j] = t)) done }
- Test program.
set -A array 11 22 33 44 55 66 77 88 99 110 shuffle echo "${array[@]}"</lang>
Ursala
This function works on lists of any type and length, including character strings. <lang Ursala>shuffle = @iNX ~&l->r ^jrX/~&l ~&lK8PrC</lang> test program: <lang Ursala>#cast %s
example = shuffle 'abcdefghijkl'</lang>
- Output:
'keacfjlbdigh'
VBA
<lang vb>Private Sub Knuth(Optional ByRef a As Variant)
Dim t As Variant, i As Integer
If Not IsMissing(a) Then
For i = UBound(a) To LBound(a) + 1 Step -1
j = Int((UBound(a) - LBound(a) + 1) * Rnd + LBound(a))
t = a(i)
a(i) = a(j)
a(j) = t
Next i
End If
End Sub Public Sub program()
Dim b As Variant, c As Variant, d As Variant, e As Variant
Randomize
'imagine an empty array on this line
b = [{10}]
c = [{10, 20}]
d = [{10, 20, 30}]
e = [{11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}]
f = [{"This ", "is ", "a ", "test"}]
Debug.Print "Before:"
Knuth 'feeding an empty array ;)
Debug.Print "After: "
Debug.Print "Before:";
For Each i In b: Debug.Print i;: Next i: Debug.Print
Knuth b
Debug.Print "After: ";
For Each i In b: Debug.Print i;: Next i: Debug.Print
Debug.Print "Before:";
For Each i In c: Debug.Print i;: Next i: Debug.Print
Knuth c
Debug.Print "After: ";
For Each i In c: Debug.Print i;: Next i: Debug.Print
Debug.Print "Before:";
For Each i In d: Debug.Print i;: Next i: Debug.Print
Knuth d
Debug.Print "After: ";
For Each i In d: Debug.Print i;: Next i: Debug.Print
Debug.Print "Before:";
For Each i In e: Debug.Print i;: Next i: Debug.Print
Knuth e
Debug.Print "After: ";
For Each i In e: Debug.Print i;: Next i: Debug.Print
Debug.Print "Before:";
For Each i In f: Debug.Print i;: Next i: Debug.Print
Knuth f
Debug.Print "After: ";
For Each i In f: Debug.Print i;: Next i: Debug.Print
End Sub</lang>
- Output:
Before:After: Before: 10 After: 10 Before: 10 20 After: 10 20 Before: 10 20 30 After: 20 10 30 Before: 11 12 13 14 15 16 17 18 19 20 21 22 After: 22 12 15 20 19 11 13 21 16 17 14 18 Before:This is a test After: a This testis
VBScript
- Implementation
<lang vb> function shuffle( a ) dim i dim r randomize timer for i = lbound( a ) to ubound( a ) r = int( rnd * ( ubound( a ) + 1 ) ) if r <> i then swap a(i), a(r) end if next shuffle = a end function
sub swap( byref a, byref b ) dim tmp tmp = a a = b b = tmp end sub</lang>
- Invocation
<lang vb>dim a a = array( 1,2,3,4,5,6,7,8,9) wscript.echo "before: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " ) wscript.echo "--" a = array( now(), "cow", 123, true, sin(1), 16.4 ) wscript.echo "before: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " )</lang>
- Output:
before: 1, 2, 3, 4, 5, 6, 7, 8, 9 after: 6, 4, 1, 2, 7, 3, 5, 8, 9 after: 8, 7, 3, 2, 6, 5, 9, 1, 4 -- before: 16/02/2010 5:46:58 PM, cow, 123, True, 0.841470984807897, 16.4 after: True, 16.4, 16/02/2010 5:46:58 PM, 123, cow, 0.841470984807897 after: 16.4, 16/02/2010 5:46:58 PM, 123, 0.841470984807897, True, cow
Vedit macro language
The shuffle routine in Playing Cards shuffles text lines in edit buffer. This example shuffles numeric registers #0 to #19.
The output will be inserted in current edit buffer. <lang vedit>// Test main
- 90 = Time_Tick // seed for random number generator
- 99 = 20 // number of items in the array
IT("Before:") IN for (#100 = 0; #100 < #99; #100++) {
#@100 = #100
Num_Ins(#@100, LEFT+NOCR) IT(" ")
} IN
Call("SHUFFLE_NUMBERS")
IT("After:") IN for (#100 = 0; #100 < #99; #100++) {
Num_Ins(#@100, LEFT+NOCR) IT(" ")
} IN Return
//-------------------------------------------------------------- // Shuffle numeric registers #0 to #nn // #99 = number of registers to shuffle (nn-1) //
- SHUFFLE_NUMBERS:
for (#91 = #99-1; #91 > 0; #91--) {
Call("RANDOM")
#101 = Return_Value
#102 = #@101; #@101 = #@91; #@91 = #102
} Return
//-------------------------------------------------------------- // Generate random numbers in range 0 <= Return_Value < #91 // #90 = Seed (0 to 0x7fffffff) // #91 = Scaling (0 to 0x10000) //
- RANDOM:
- 92 = 0x7fffffff / 48271
- 93 = 0x7fffffff % 48271
- 90 = (48271 * (#90 % #92) - #93 * (#90 / #92)) & 0x7fffffff
Return ((#90 & 0xffff) * #91 / 0x10000)</lang>
- Output:
Before: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 After: 9 13 8 18 10 1 17 15 0 16 14 19 3 2 7 11 6 4 5 12
Vlang
Updated to Vlang version 0.2.2 <lang go>import rand import rand.seed
fn shuffle(mut arr []int) {
for i := arr.len - 1; i >= 0; i-- {
j := rand.intn(i + 1)
arr[i], arr[j] = arr[j], arr[i]
}
println('After Shuffle: $arr')
}
fn main() {
seed_array := seed.time_seed_array(2)
rand.seed(seed_array)
mut arr := [6, 9, 1, 4]
println('Input: $arr')
shuffle(mut arr)
shuffle(mut arr)
println('Output: $arr')
} </lang>
- Output:
Input: [6, 9, 1, 4] After Shuffle: [6, 1, 4, 9] After Shuffle: [4, 9, 1, 6] Output: [4, 9, 1, 6]
Wren
<lang ecmascript>import "random" for Random
var rand = Random.new()
var knuthShuffle = Fn.new { |a|
var i = a.count - 1
while (i >= 1) {
var j = rand.int(i + 1)
var t = a[i]
a[i] = a[j]
a[j] = t
i = i - 1
}
}
var tests = [ [], [10], [10, 20], [10, 20, 30] ] for (a in tests) {
var b = a.toList // store original order
knuthShuffle.call(a)
System.print("%(b) -> %(a)")
}</lang>
- Output:
Sample run:
[] -> [] [10] -> [10] [10, 20] -> [20, 10] [10, 20, 30] -> [30, 10, 20]
zkl
Two versions, imperative and functional, same results. xs has to be a mutable list. <lang zkl>fcn kshuffle(xs){
foreach i in ([xs.len()-1..1,-1]){ xs.swap(i,(0).random(0,i+1)) }
xs
} fcn kshufflep(xs){
[xs.len()-1..1,-1].pump(Void,'wrap(i){ xs.swap(i,(0).random(0,i+1)) })
xs
}</lang>
var ns=(1).pump(10,List).copy() // [1..10] made mutable
kshuffle(ns) //-->L(6,3,8,2,4,5,10,9,1,7)
ns="this is a test foo bar hoho".split(" ").copy();
kshufflep(ns) //-->L("a","bar","hoho","foo","test","is","this")
- Programming Tasks
- Classic CS problems and programs
- 11l
- 360 Assembly
- 6502 Assembly
- AArch64 Assembly
- ACL2
- Action!
- Ada
- Aime
- ALGOL 68
- AppleScript
- ARM Assembly
- Arturo
- AutoHotkey
- AutoIt
- AWK
- BASIC
- Applesoft BASIC
- Sinclair ZX81 BASIC
- BBC BASIC
- IS-BASIC
- QB64
- Bc
- BQN
- Brat
- C
- C sharp
- C++
- Clojure
- CLU
- CMake
- COBOL
- CoffeeScript
- Common Lisp
- Crystal
- D
- Delphi
- DWScript
- E
- EasyLang
- EchoLisp
- Egel
- Eiffel
- Elena
- Elixir
- Erlang
- ERRE
- Euphoria
- F Sharp
- Factor
- Fantom
- Forth
- Fortran
- FreeBASIC
- Frink
- FunL
- Gambas
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Inform 6
- J
- Java
- JavaScript
- Joy
- Jq
- Julia
- Kotlin
- LabVIEW
- Lambdatalk
- Lasso
- Liberty BASIC
- Logo
- Lua
- M2000 Interpreter
- M4
- Mathematica
- Wolfram Language
- MATLAB
- Maxima
- Modula-3
- MUMPS
- Nemerle
- NetRexx
- Nim
- Objective-C
- OCaml
- Oforth
- Ol
- Oz
- PARI/GP
- Pascal
- Perl
- Phix
- PHP
- PicoLisp
- PL/I
- PowerShell
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- REBOL
- REXX
- Ring
- Ruby
- Run BASIC
- Rust
- Rand
- Scala
- Scheme
- Scratch
- Seed7
- SenseTalk
- Sidef
- Smalltalk
- SNOBOL4
- Stata
- Swift
- Tcl
- TI-83 BASIC
- TUSCRIPT
- UBasic/4tH
- UNIX Shell
- Ursala
- VBA
- VBScript
- Vedit macro language
- Vlang
- Wren
- Zkl