Knuth shuffle: Difference between revisions
→{{header|Uiua}}
Walterpachl (talk | contribs) m (→version 2: typo) |
|||
(245 intermediate revisions by 97 users not shown) | |||
Line 1:
{{task|Classic CS problems and programs}}
The [[wp:Knuth shuffle|Knuth shuffle]] (a.k.a. the Fisher-Yates shuffle) is an algorithm for randomly shuffling the elements of an array.
;Task:
Implement the Knuth shuffle for an integer array (or, if possible, an array of any type).
;Specification:
Given an array '''''items''''' with indices ranging from ''0'' to '''''last''''', the algorithm can be defined as follows (pseudo-code):
'''for''' ''i'' '''from''' ''last'' '''downto''' 1 '''do''':
'''let''' ''j'' = random integer in range ''0'' <math>\leq</math> ''j'' <math>\leq</math> ''i''
'''swap''' ''items''[''i''] '''with''' ''items''[''j'']
;Notes:
* 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:
::::::{| class="wikitable"
|-
! Input array
! Possible output arrays
|-
| <tt>[]</tt>
| <tt>[]</tt>
|-
| <tt>[10]</tt>
| <tt>[10]</tt>
|-
| <tt>[10, 20]</tt>
| <tt>[10, 20]</tt><br><tt>[20, 10]</tt>
|-
| <tt>[10, 20, 30]</tt>
| <tt>[10, 20, 30]</tt><br><tt>[10, 30, 20]</tt><br><tt>[20, 10, 30]</tt><br><tt>[20, 30, 10]</tt><br><tt>[30, 10, 20]</tt><br><tt>[30, 20, 10]</tt>
|}
(These are listed here just for your convenience; no need to demonstrate them on the page.)
;Related task:
* [[Sattolo cycle]]
{{Template:Strings}}
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight 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)</syntaxhighlight>
{{out}}
<pre>
shuffled: [0, 5, 7, 1, 3, 8, 4, 6, 9, 2]
</pre>
=={{header|360 Assembly}}==
{{trans|BBC BASIC}}
<syntaxhighlight 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
</syntaxhighlight>
{{out}}
<pre>
13 16 10 18 19 14 6 17 2 5 1 15 7 11 12 9 8 20 4 3
</pre>
=={{header|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 <code>$FE</code> 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.
<syntaxhighlight 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</syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight 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"
</syntaxhighlight>
=={{header|ACL2}}==
<
(defun array-swap (name array i j)
Line 26 ⟶ 369:
array
(1- (first (dimensions name array)))
state))</
=={{header|Action!}}==
<syntaxhighlight 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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Knuth_shuffle.png Screenshot from Atari 8-bit computer]
<pre>
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
</pre>
=={{header|Ada}}==
This implementation is a generic shuffle routine, able to shuffle an array of any type.
<
type Element_Type is private;
type Array_Type is array (Positive range <>) of Element_Type;
procedure Generic_Shuffle (List : in out Array_Type);</
<
procedure Generic_Shuffle (List : in out Array_Type) is
Line 51 ⟶ 448:
List(K) := T;
end loop;
end Generic_Shuffle;</
An example using Generic_Shuffle.
<
with Generic_Shuffle;
Line 74 ⟶ 471:
Ada.Text_IO.Put(Integer'Image(Integer_List(I)));
end loop;
end Test_Shuffle;</
=={{header|Aime}}==
The shuffle function works on any type (the lists are heterogenous).
<
shuffle(list l)
{
integer i;
i =
if (i) {
i -= 1;
while (i) {
i -= 1;
}
}
}</
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G}}
<
(
ENTIER (random * ABS (b-a+1) + (a<b|a|b))
Line 108 ⟶ 505:
a[j] := t
OD
);</
<
[20]INT a;
FOR i FROM 1 TO 20 DO a[i] := i OD;
knuth shuffle(a);
print(a)
)</
=={{header|Amazing Hopper}}==
<syntaxhighlight lang="c">
#include <basico.h>
algoritmo
v={},n=19
'0,1,2,3,4,5,6,7,8,9,"\t","\v","\v","A","B","C","D","E","F"' enlistar en 'v'
imprimir ("Original:\n[",v,"]\n\n")
imprimir (rareti( n, #(ceil(rand(n))), n, intercambiar en (v)),\
"Processed:\n[", v,"]\n" )
terminar
</syntaxhighlight>
{{out}}
<pre>
Original:
[0,1,2,3,4,5,6,7,8,9, ,
,
,A,B,C,D,E,F]
Processed:
[F,B, ,1,9,
,2,D,5,6,4,8,C,7,A,
,3,0,E]
</pre>
=={{header|AppleScript}}==
===Iteration===
<syntaxhighlight lang="applescript">set n to 25
set array to {}
Line 130 ⟶ 558:
end repeat
return {unshuffled, shuffled}</
Example:
<
{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}}</
----
Better:
<syntaxhighlight 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)</syntaxhighlight>
{{output}}
''eg.''
<syntaxhighlight lang="applescript">{"Golf", "Foxtrot", "Echo", "Delta", "Kilo", "Charlie", "Mike", "Alpha", "Lima", "Juliett", "India", "Bravo", "Hotel"}</syntaxhighlight>
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:
<syntaxhighlight 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</syntaxhighlight>
----
===Functional composition===
<syntaxhighlight 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</syntaxhighlight>
{{Out}}
e.g.
<syntaxhighlight lang="applescript">{"mu", "theta", "alpha", "delta", "zeta", "gamma",
"iota", "kappa", "lambda", "epsilon", "beta", "eta"}</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight 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
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight 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]</syntaxhighlight>
=={{header|AutoHotkey}}==
ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=133 discussion]
<
MsgBox % shuffle("1,2,3,4,5,6,7,8,9")
Line 149 ⟶ 972:
s .= "," . a%A_Index%
Return SubStr(s,2) ; drop leading comma
}</
For Arrays:
[https://www.autohotkey.com/boards/viewtopic.php?f=6&t=79152 to MsgBox it, you can use p()]
[https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array#6274381 (translated from)]
<syntaxhighlight 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
}</syntaxhighlight>
=={{header|AutoIt}}==
<syntaxhighlight lang="autoit">
Dim $a[10]
ConsoleWrite('array before permutation:' & @CRLF)
Line 178 ⟶ 1,024:
Next
EndFunc
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|AWK}}==
Many [[Arrays#AWK|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.
<syntaxhighlight lang="awk"># Shuffle an _array_ with indexes from 1 to _len_.
function shuffle(array, len, i, j, t) {
for (i = len; i > 1; i--) {
Line 208 ⟶ 1,058:
for (i = 1; i < len; i++) printf "%s ", array[i]
printf "%s\n", array[len]
}</
=={{header|BASIC}}==
<
DIM cards(51) AS INTEGER
Line 231 ⟶ 1,081:
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT
PRINT</
{{out}}
<pre>
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
Line 240 ⟶ 1,091:
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
</pre>
==={{header|
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 <code>150</code> initializes and prints each element in the array. Line <code>190</code> performs the swap of the elements.
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>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</pre>
When it has finished, the screen will show (for example):
<pre>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</pre>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> cards% = 52
DIM pack%(cards%)
FOR I% = 1 TO cards%
Line 253 ⟶ 1,127:
PRINT pack%(I%);
NEXT I%
PRINT</
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
==={{header|GW-BASIC}}===
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
{{works with|Chipmunk Basic}}
<syntaxhighlight lang="qbasic">100 CLS
110 RANDOMIZE TIMER
120 DIM CARDS(51)
130 PRINT "before:"
140 FOR L0 = 0 TO 51
150 CARDS(L0) = L0
160 PRINT STR$(CARDS(L0));" ";
170 NEXT L0
180 FOR L0 = 51 TO 0 STEP -1
190 CARD = INT(RND(1)*(L0+1))
200 IF CARD <> L0 THEN T = CARDS(CARD) : CARDS(CARD) = CARDS(L0) : CARDS(L0) = T
210 NEXT L0
220 PRINT : PRINT
230 PRINT "after:"
240 FOR L0 = 0 TO 51
250 PRINT STR$(CARDS(L0));" ";
260 NEXT L0
270 PRINT
280 END</syntaxhighlight>
==={{header|IS-BASIC}}===
<syntaxhighlight 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</syntaxhighlight>
==={{header|Minimal BASIC}}===
<syntaxhighlight lang="qbasic">100 REM Knuth shuffle
110 RANDOMIZE
120 DIM B(51)
130 PRINT "BEFORE:"
140 FOR L0 = 0 TO 51
150 LET B(L0) = L0
160 PRINT B(L0);" ";
170 NEXT L0
180 FOR L0 = 51 TO 0 STEP -1
190 LET C = INT(RND*(L0+1))
200 IF C <> L0 THEN 220
210 GOTO 250
220 LET T = B(C)
230 LET B(C) = B(L0)
240 LET B(L0) = T
250 NEXT L0
260 PRINT
270 PRINT
280 PRINT "AFTER:"
290 FOR L0 = 0 TO 51
300 PRINT B(L0);" ";
310 NEXT L0
320 PRINT
330 END</syntaxhighlight>
==={{header|OxygenBasic}}===
<syntaxhighlight lang="text">uses chaos
uses timeutil
seed=GetTickCount
int i,j
int d[100] 'int array or any other type
...
for i=100 to 1 step -1
j=irnd(1,100)
swap d[i],d[j]
next</syntaxhighlight>
==={{header|QB64}}===
Shuffle and make sure that number does not take its place<br/>
and between cells at least 10% ... Shuffle from Russia
<syntaxhighlight lang="qbasic">
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</syntaxhighlight>
==={{header|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 <code>10</code> seeds the pseudo-random number generator. Note that strings (and arrays) are indexed from 1.
The program works with the unexpanded (1k RAM) ZX81.
<syntaxhighlight 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</syntaxhighlight>
{{out}}
While the program is running, we will see something like this (using lower case as a stand-in for inverse video):
<pre>ABCuEFGzwJKLMNOPxySvdtiqrh</pre>
When it has finished, the screen will show (for example):
<pre>lcjbpxekzsaygumwnovfdtiqrh</pre>
==={{header|True BASIC}}===
{{trans|BASIC}}
<syntaxhighlight lang="qbasic">OPTION BASE 0
RANDOMIZE
DIM cards(51)
PRINT "before:"
FOR L0 = 0 TO 51
LET cards(L0) = L0
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT L0
FOR L0 = 51 TO 0 STEP -1
LET card = INT(RND * (L0 + 1))
IF card <> L0 THEN
LET t = cards(lb + L0)
LET cards(lb + L0) = cards(lb + card)
LET cards(lb + card) = t
END IF
NEXT L0
PRINT
PRINT "after:"
FOR L0 = 0 TO 51
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT L0
END</syntaxhighlight>
{{out}}
<pre>Same as BASIC entry.</pre>
==
I provide a <tt>shuffle()</tt> 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 <tt>shuffle[]</tt>; the array is not a function parameter because <tt>bc</tt> passes arrays by copying.
This code requires a <tt>bc</tt> with long names; the test program also requires a <tt>bc</tt> with the <tt>print</tt> statement.
{{works with|OpenBSD bc}}
<
scale = 0
Line 303 ⟶ 1,353:
trash = shuffle(10)
"Shuffled array: "; trash = print_array(10)
quit</
{{out}}
<pre>Original array: 11, 22, 33, 44, 55, 66, 77, 88, 99, 110
Shuffled array: 66, 44, 11, 55, 33, 77, 110, 22, 88, 99</pre>
=={{header|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.
<syntaxhighlight 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⟩</syntaxhighlight>
[https://mlochbaum.github.io/BQN/try.html#code=S251dGgg4oaQIHsKICDwnZWKIGFycjoKICBsIOKGkCDiiaBhcnIKICB7CiAgICBhcnIg4oapIOKMveKMvijin6jigKJyYW5kLlJhbmdlIGwsIPCdlanin6niirjiio8pYXJyCiAgfcKo4oaVbAogIGFycgp9ClAg4oaQIOKAolNob3cgS251dGgKClAg4p+o4p+pClAg4p+oMTDin6kKUCDin6gxMCwgMjDin6kKUCDin6gxMCwgMjAsIDMw4p+p Try It!]
=={{header|Brat}}==
<
(a.length - 1).to 1 { i |
random_index = random(0, i)
Line 319 ⟶ 1,391:
}
p shuffle [1 2 3 4 5 6 7]</
=={{header|C}}==
This shuffles any "object"; it imitates <tt>qsort</tt> in the syntax.
<
#include <string.h>
Line 343 ⟶ 1,415:
}
free(temp);
} </
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:
<
#include <stdlib.h>
Line 396 ⟶ 1,468:
printf(" %d", x[i]);
return 0;
}</
=={{header|C sharp|C#}}==
<syntaxhighlight 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;
}
}</syntaxhighlight>
=={{header|C++}}==
'''Compiler:''' [[g++]] (version 4.3.2 20081105 (Red Hat 4.3.2-7))
<
#include <algorithm>
#include <iterator>
Line 406 ⟶ 1,489:
template<typename RandomAccessIterator>
void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
if(begin == end) {
return;
}
for(unsigned int n = end - begin - 1; n >= 1; --n) {
unsigned int k = rand() % (n + 1);
Line 412 ⟶ 1,498:
}
}
}</
The standard library provides this in the form of <code>std::random_shuffle</code>.
<
#include <vector>
Line 424 ⟶ 1,510:
std::random_shuffle(array, array + 9); // shuffle C-style array
std::random_shuffle(vec.begin(), vec.end()); // shuffle STL container
}</
=={{header|Clojure}}==
<
(reduce (fn [v i] (let [r (rand-int i)]
(assoc v i (v r) r (v i))))
vect (range (dec (count vect)) 1 -1)))</
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.
=={{header|
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>7 9 2 3 4 8 1 6 5</pre>
(Or any other order.)
=={{header|CMake}}==
<
# stores the result in a list.
function(shuffle var)
Line 508 ⟶ 1,578:
endforeach(i)
set("${var}" ${answer} PARENT_SCOPE)
endfunction(shuffle)</
<
message(STATUS "${result}")
# One possible output:
# -- 66;33;22;55;44;11</
=={{header|COBOL}}==
<syntaxhighlight 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
.</syntaxhighlight>
=={{header|CoffeeScript}}==
{{trans|JavaScript}}
<
n = a.length
while n > 1
Line 537 ⟶ 1,638:
for key, val of counts
console.log "#{key}: #{val}"</
{{out}}
<pre>
> coffee knuth_shuffle.coffee
Line 550 ⟶ 1,651:
=={{header|Common Lisp}}==
<
(loop for i from (length sequence) downto 2
do (rotatef (elt sequence (random i))
(elt sequence (1- i))))
sequence)</
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 <code>aref</code> rather than <code>elt</code>):
<
(etypecase sequence
(list (nshuffle-list sequence))
Line 571 ⟶ 1,672:
do (rotatef (aref array (random i))
(aref array (1- i)))
finally (return array)))</
=={{header|Crystal}}==
<syntaxhighlight 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</syntaxhighlight>
=={{header|D}}==
===Standard Version===
A variant of the Knuth shuffle is in the D standard library Phobos:
<
import std.stdio, std.random;
Line 582 ⟶ 1,694:
a.randomShuffle;
a.writeln;
}</
{{out}}
<pre>[8, 9, 3, 1, 7, 5, 4, 6, 2]</pre>
Line 588 ⟶ 1,700:
===One Implementation===
This shuffles any collection that supports random access, length and swapping of items:
<
void knuthShuffle(Range)(Range r)
if (isRandomAccessRange!Range && hasLength!Range &&
hasSwappableElements!Range) {
foreach_reverse (immutable i, ref ri; r[1 ..
}
Line 601 ⟶ 1,713:
a.knuthShuffle;
a.writeln;
}</
=={{header|Delphi}}==
=={{header|DWScript}}==
<
var
i, j, tmp : Integer;
Line 615 ⟶ 1,727:
tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;
end;
end;</
=={{header|E}}==
<
for bound in (2..(array.size())).descending() {
def i := random.nextInt(bound)
Line 626 ⟶ 1,738:
array[i] := t
}
}</
<
# 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()</
=={{header|EasyLang}}==
<syntaxhighlight>
proc shuffle . a[] .
for i = len a[] downto 2
r = randint i
swap a[r] a[i]
.
.
arr[] = [ 1 2 3 ]
shuffle arr[]
print arr[]
</syntaxhighlight>
=={{header|EchoLisp}}==
<syntaxhighlight 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)
</syntaxhighlight>
=={{header|Egel}}==
<syntaxhighlight 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)
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight 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
</syntaxhighlight>
{{out}}
<pre>
Initial: 1 2 3 4 5 6 7
Shuffeld: 1 5 3 4 7 6 2
</pre>
=={{header|Elena}}==
ELENA 6.x:
<syntaxhighlight 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.nextInt(i,max);
self.exchange(i,j)
};
^ self
}
}
public program()
{
var a := Array.allocate(MAX).populate::(i => i );
console.printLine(a.randomize())
}</syntaxhighlight>
{{out}}
<pre>
3,8,4,5,1,2,6,0,7,9
</pre>
=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight 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)</syntaxhighlight>
{{out}}
<pre>
[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}
</pre>
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module( knuth_shuffle ).
Line 650 ⟶ 1,965:
Item = lists:nth( random:uniform(N), Inputs ),
{lists:delete(Item, Inputs), [Item | Acc]}.
</syntaxhighlight>
{{out}}
<pre>
Line 656 ⟶ 1,971:
[5,7,8,1,4,2,3,9,6]
</pre>
=={{header|ERRE}}==
<syntaxhighlight 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
</syntaxhighlight>
=={{header|Euphoria}}==
{{trans|BASIC}}
<
cards = repeat(0,52)
integer card,temp
Line 681 ⟶ 2,018:
for i = 1 to 52 do
printf(1,"%d ",cards[i])
end for</
=={{header|F_Sharp|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:
<syntaxhighlight 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</syntaxhighlight>
Here's the modified Knuth shuffle which shuffles the original array in place
<syntaxhighlight 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</syntaxhighlight>
Example:
<syntaxhighlight lang="fsharp">> KnuthShuffle [| "Darrell"; "Marvin"; "Doug"; "Greg"; "Sam"; "Ken" |];;
val it : string array = [|"Marvin"; "Doug"; "Sam"; "Darrell"; "Ken"; "Greg"|]</syntaxhighlight>
=={{header|Factor}}==
There is a <code>randomize</code> word already in the standard library. Implementation:
<
dup length [ dup 1 > ]
[ [ iota random ] [ 1 - ] bi [ pick exchange ] keep ]
while drop ;</
=={{header|Fantom}}==
<
{
static Void knuthShuffle (List array)
Line 712 ⟶ 2,085:
echo (b)
}
}</
=={{header|Forth}}==
<
: shuffle ( deck size -- )
Line 729 ⟶ 2,102:
create deck 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,
deck 10 2dup shuffle .array</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 765 ⟶ 2,138:
end subroutine Shuffle
end program Knuth_Shuffle</
=={{header|
<syntaxhighlight 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)
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
Dim As ULong
Randomize Timer
For i = 0 To n -2
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</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Frink}}==
The built-in method <CODE><I>array</I>.shuffle[]</CODE> implements the Fisher-Yates-Knuth shuffle algorithm:
<syntaxhighlight lang="frink">
a = [1,2,3]
a.shuffle[]
</syntaxhighlight>
=={{header|FunL}}==
<syntaxhighlight 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()</syntaxhighlight>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
void local fn KnuthShuffle( mutArr as CFMutableArrayRef )
NSUInteger i, j, count
count = len(mutArr)
for i = count-1 to 1 step -1
j = rnd(i+1)-1
MutableArrayExchangeObjects( mutArr, i, j )
next
end fn
randomize
CFMutableArrayRef mutArr
NSUInteger i
mutArr = fn MutableArrayWithObjects( @0, @1, @2, @3, @4, @5, @6, @7, @8, @9, NULL )
NSLog( @"Before shuffle: %@", fn ArrayComponentsJoinedByString( mutArr, @"" ) )
for i = 1 to 100
fn KnuthShuffle( mutArr )
NSLog( @"%@", fn ArrayComponentsJoinedByString( mutArr, @"" ) )
next
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Before shuffle: 0123456789
1274860395
2715638904
7182035964
1297658403
2916574083
9162507843
1875962034
8721965034
7968402351
9347510862
</pre>
=={{header|Gambas}}==
'''[https://gambas-playground.proko.eu/?gist=58402023fbdc617ce10f6a85db721105 Click this link to run this code]'''
<syntaxhighlight 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</syntaxhighlight>
Output:
<pre>
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
</pre>
=={{header|GAP}}==
<
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 ->
ShuffleAlt([1 .. 10]);
Line 829 ⟶ 2,358:
# 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)</
=={{header|Go}}==
(Note, in addition to these examples,
<code>[https://golang.org/pkg/math/rand/#Shuffle rand.Shuffle]</code>
was added in [https://golang.org/doc/go1.10#math/rand Go1.10]
implementing a Fisher–Yates shuffle.)
<syntaxhighlight lang="go">package main
import (
Line 853 ⟶ 2,387:
}
fmt.Println(a)
}</
To shuffle any type:
<
import (
Line 902 ⟶ 2,436:
shuffle(a)
fmt.Println(a)
}</
{{out|Example output}} (of either program)
<pre>
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]
Line 911 ⟶ 2,445:
=={{header|Groovy}}==
Solution:
<
if (list == null || list.empty) return list
def r = new Random()
Line 920 ⟶ 2,454:
}
list
}</
Test:
<
println list
println shuffle(list)
println shuffle(list)
println shuffle(list)</
{{out}}
<pre>[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]
Line 934 ⟶ 2,468:
=={{header|Haskell}}==
<
mkRands
mkRands = mapM (randomRIO . (,) 0) . enumFromTo 1 . pred
replaceAt :: Int -> a -> [a] -> [a]
replaceAt i c
let (a, b) = splitAt i l
in a ++ c : drop 1 b
swapElems :: (Int, Int) -> [a] -> [a]
swapElems (i, j)
| 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)</syntaxhighlight>
or, as an alternative to making two indexed references into the list with '''(!!)''':
<syntaxhighlight 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</syntaxhighlight>
Examples of use of either of the two versions above:
<pre>*Main> knuthShuffle ['a'..'k']
"bhjdgfciake"
Line 958 ⟶ 2,517:
[(0,10),(8,18),(2,12),(3,13),(9,19),(4,14),(7,17),(1,11),(6,16),(5,15)]</pre>
Function for showing intermediate results:
<
knuthShuffleProcess =
(mapM_ print. reverse =<<). ap (fmap. (. zip [1..]). scanr swapElems) (mkRands. length)</
<pre>*Main> knuthShuffleProcess ['a'..'k']
"abcdefghijk"
Line 975 ⟶ 2,534:
"iebjhkcgfad"</pre>
An imperative implementation using arrays and the <code>ST</code> monad:
<
import Data.STRef
import Control.Monad
Line 995 ⟶ 2,554:
where len = length list
newAry :: (Int, Int) -> [a] -> ST s (STArray s Int a)
newAry = newListArray</
=={{header|Icon}} and {{header|Unicon}}==
The <tt>shuffle</tt> method used here can shuffle lists, record fields, and strings:
<
show(shuffle([3,1,4,1,5,9,2,6,3]))
show(shuffle("this is a string"))
Line 1,012 ⟶ 2,571:
every writes(!A," ")
write()
end</
{{out}}
<pre>->ks
9 6 1 4 3 1 3 5 2
Line 1,019 ⟶ 2,578:
-></pre>
Note that the gloriously succinct 'standard' Icon shuffle:
<
every !A :=: ?A
end</
is subtly biased.
=={{header|Inform 6}}==
<
for (i = n - 1: i > 0: i--) {
j = random(i + 1) - 1;
tmp = a->j;
a->j = a->i;
a->i = tmp;
}
];</
=={{header|J}}==
<
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.
<
fold swap transform array <==> f / g y</
Example of a transformed input:
<
0 0 0 0 0 0
1 1 0 0 0 0
Line 1,050 ⟶ 2,608:
4 3 0 0 0 0
5 0 0 0 0 0
0 1 2 3 4 5</
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:
<
Finally, the shuffled indexes select elements from the original array.
<syntaxhighlight lang
Alternatively, instead of creating a rectangular array, the swapping indices and the original data can be individually boxed.
Line 1,062 ⟶ 2,620:
With this approach, the data structure with the swapping indices and the original data could look like this:
<
+---+-+---+---+-+-----+
|4 2|3|2 1|1 0|0|abcde|
+---+-+---+---+-+-----+</
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 (<code>C.</code>)).
The resulting definition looks like this:
<
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:<
5 6 7 8 9 10 11 12 13</
<
13 10 7 5 11 9 8 6 12</
<
1 1 1
1 0 0
Line 1,089 ⟶ 2,647:
11 2 3
0 11 2</
<
11 2 3
0 11 2
Line 1,101 ⟶ 2,659:
1 2 3
2 3 4</
<
+--+---+----+---+
|aA|bbB|cC%$|dD@|
+--+---+----+---+</
<
+--+----+---+---+
|aA|cC%$|dD@|bbB|
+--+----+---+---+</
In J the shuffling of an arbitrary array can easily be implemented by the phrase
( ref http://www.jsoftware.com/jwiki/JPhrases/RandomNumbers ):
<syntaxhighlight lang
Applied on the former examples:
<
8 7 13 6 10 11 5 9 12
Line 1,133 ⟶ 2,691:
+----+---+--+---+
|cC%$|bbB|aA|dD@|
+----+---+--+---+</
=={{header|Java}}==
<
public static final Random gen = new Random();
Line 1,159 ⟶ 2,717:
array[k] = temp;
}
}</
=={{header|JavaScript}}==
===ES5===
<syntaxhighlight lang="javascript">function knuthShuffle(arr) {
var rand, temp,
for (i = arr.length - 1; i > 0; i -= 1) {
rand = Math.floor((i + 1) * Math.random());//get random between zero and i (inclusive)
temp =
}
return
}
var res
'1,2,3': 0, '1,3,2': 0,
'2,1,3': 0, '2,3,1': 0,
Line 1,185 ⟶ 2,741:
};
for (var i = 0; i < 100000; i++) {
res[
}
for (var key in res) {
print(key + "\t" + res[key]);
}</
Results in:
<pre>1,2,3 16619
Line 1,199 ⟶ 2,756:
3,2,1 16596</pre>
==
====Mutating in-place swap====
<syntaxhighlight 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();
})();
</syntaxhighlight>
{{Out}}
e.g.
<syntaxhighlight lang="javascript">["iota", "epsilon", "kappa", "theta", "gamma", "delta",
"lambda", "eta", "zeta", "beta", "mu", "alpha"]</syntaxhighlight>
====Non-mutating swap====
<syntaxhighlight 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();
})();</syntaxhighlight>
{{Out}}
e.g.
<syntaxhighlight lang="javascript">["mu", "theta", "beta", "eta", "delta", "epsilon",
"kappa", "alpha", "gamma", "lambda", "zeta", "iota"]</syntaxhighlight>
=={{header|Joy}}==
<syntaxhighlight 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.</
Using knuth-shuffle (file shuffle.joy):
<
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
knuth-shuffle.</
Command line:
: <tt>joy shuffle.joy</tt>
{{out}}
<pre>
usrlib is loaded
Line 1,230 ⟶ 2,905:
[12 6 8 4 14 18 7 15 1 0 11 13 5 10 16 2 19 17 9 20 3]
</pre>
=={{header|jq}}==
{{works with|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:
<syntaxhighlight 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)
</syntaxhighlight>
{{out}}
<pre>
[]
[10,20]
[20,30,10]
</pre>
<p style="font-size:36px">
🂶🃚🃈🃘🃊🂥🃉🂽🂣🂸🃂🂺🃗<br>
🂵🃁🃇🂮🂹🃝🃆🂱🂻🂩🃋🂭🃖<br>
🂢🃛🃕🃃🂾🃙🃞🂨🂪🂲🂷🃍🂫<br>
🂦🃒🃔🂳🂡🃓🃄🂴🃅🃎🃑🂤🂧
</p>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight 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))</syntaxhighlight>
{{out}}
<pre># 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]</pre>
=={{header|Kotlin}}==
<syntaxhighlight 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())
}
}</syntaxhighlight>
{{out}}
<pre>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]</pre>
=={{header|LabVIEW}}==
Line 1,236 ⟶ 3,055:
[[File:Knuth_shuffle_diagram.png|200px]]
=={{header|Lambdatalk}}==
<syntaxhighlight 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]
</syntaxhighlight>
=={{header|Lasso}}==
<
fail_if(
#p1 < 1 or #p2 < 1 or
Line 1,257 ⟶ 3,108:
}
(1 to 10)->asStaticArray->knuthShuffle&asString</
{{out}}
<pre>staticarray(9, 5, 6, 1, 10, 8, 3, 4, 2, 7)</pre>
=={{header|Liberty BASIC}}==
<
UpperBound = 9
Dim array(UpperBound)
Line 1,284 ⟶ 3,134:
For i = 0 To UpperBound
Print array(i)
Next i</
=={{header|Logo}}==
<
localmake "t item :i :a
setitem :i :a item :j :a
Line 1,298 ⟶ 3,148:
make "a {1 2 3 4 5 6 7 8 9 10}
shuffle :a
show :a</
Lhogho does not have a setitem, and also does things more 'function'ally.
<
local "res
make "res []
Line 1,336 ⟶ 3,186:
make "a ( list 1 2 3 4 5 6 7 8 9 10 )
make "a shuffle :a
show :a</
=={{header|Lua}}==
<
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</
=={{header|M2000 Interpreter}}==
<syntaxhighlight 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()
}
</syntaxhighlight>
=={{header|M4}}==
<
define(`randSeed',141592653)
define(`rand_t',`eval(randSeed^(randSeed>>13))')
Line 1,381 ⟶ 3,244:
show(`b')
shuffle(`b')
show(`b')</
{{out}}
<pre>
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
Line 1,393 ⟶ 3,256:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Usage of built-in function:
<
Custom function:
<
Module[{indices = {}, allindices = Range[Length[input]]},
Do[
Line 1,406 ⟶ 3,269:
];
input[[indices]]
]</
Example:
<
=={{header|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.
<
for i = (numel(list):-1:2)
Line 1,421 ⟶ 3,284:
list([j i]) = list([i j]);
end
end</
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.
<syntaxhighlight lang="matlab">function list = randSort(list)
list = list( randperm(numel(list)) );
end</
=={{header|Maxima}}==
<
random_permutation([a, b, c]);</
=={{header|Modula-3}}==
<
IMPORT IO, Fmt, Random;
Line 1,462 ⟶ 3,328:
END;
IO.Put("\n");
END Shuffle.</
{{out}}
<pre>
martin@thinkpad:~$ ./shuffle
Line 1,472 ⟶ 3,338:
=={{header|MUMPS}}==
<
Set list="",n=0
Set ii="" For Set ii=$Order(items(ii)) Quit:ii="" Do
Line 1,555 ⟶ 3,421:
Queen of Spades
King of Diamonds
5 of Clubs</
=={{header|Nemerle}}==
<
{
def rnd = Random();
Line 1,565 ⟶ 3,431:
arr[i] <-> arr[(rnd.Next(i, arr.Length))];
arr
}</
=={{header|NetRexx}}==
===version 1===
<syntaxhighlight lang="netrexx">/* NetRexx */
options replace format comments java crossref savelog symbols nobinary
Line 1,616 ⟶ 3,483:
say
return</
{{out}}
<pre>
[hA, h2, h3, h4, h5, h6, h7, h8, h9, h10, hJ, hQ, hK]
Line 1,628 ⟶ 3,495:
[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]
</pre>
===version 2===
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>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]</pre>
=={{header|Nim}}==
Note that the function "shuffle" exists in the standard module "random" and that it uses the Knuth shuffle.
<syntaxhighlight 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</syntaxhighlight>
=={{header|Objective-C}}==
<syntaxhighlight 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;
}</syntaxhighlight>
{{out}}
<pre>
(
9,
4,
0,
8,
5,
3,
2,
1,
7,
6
)
</pre>
=={{header|OCaml}}==
<
for n = Array.length arr - 1 downto 1 do
let k = Random.int (n + 1) in
Line 1,637 ⟶ 3,605:
arr.(n) <- arr.(k);
arr.(k) <- temp
done</
=={{header|Oforth}}==
Works with any object that has the property to be Indexable (Lists, Intervals, ...)
Returns a new list
<syntaxhighlight 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 ; </syntaxhighlight>
=={{header|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.
<syntaxhighlight 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)))))))
</syntaxhighlight>
Testing:
<syntaxhighlight 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))
</syntaxhighlight>
Output:
<pre>
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)
</pre>
=={{header|Oz}}==
<
proc {Shuffle Arr}
Low = {Array.low Arr}
Line 1,658 ⟶ 3,678:
{Show {Array.toRecord unit X}}
{Shuffle X}
{Show {Array.toRecord unit X}}</
=={{header|PARI/GP}}==
<
forstep(n=#v,2,-1,
my(i=random(n)+1,t=v[i]);
Line 1,670 ⟶ 3,690:
};
FY(vector(52,i,i))</
=={{header|Pascal}}==
<
const
max = 11;
type
tmylist = array [startIdx..startIdx+max-1] of tmyData;
procedure
var
i
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
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:
i: integer;
begin
randomize;
InitList(a);
writeln;
For i := 0 to 4 do
shuffleList(a);
DisplayList(a);
end;
end.</syntaxhighlight>
{{out}}
<pre> -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</pre>
=={{header|Perl}}==
<
my @a = @_;
foreach my $n (1 .. $#a) {
Line 1,717 ⟶ 3,762:
}
return @a;
}</
=={{header|
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cards</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">52</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Before: "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">cards</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">52</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">cards</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">],</span><span style="color: #000000;">cards</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cards</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">cards</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"After: "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">cards</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Sorted: "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cards</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre style="font-size: 12px">
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}
</pre>
=={{header|PHP}}==
<
function yates_shuffle($arr){
$shuffled = Array();
Line 1,749 ⟶ 3,800:
list($arr[$i], $arr[$rnd]) = array($arr[$rnd], $arr[$i]);
}
}</
=={{header|Picat}}==
<syntaxhighlight lang="picat">go =>
_ = random2(),
L = 1..10,
println(l_before=L),
knuth_shuffle(L),
println('l_after '=L),
nl.
knuth_shuffle(L) =>
foreach(I in L.len..-1..1)
J = random(1,I),
Tmp = L[I],
L[I] := L[J],
L[J] := Tmp
end.</syntaxhighlight>
{{out}}
<pre>l_before = [1,2,3,4,5,6,7,8,9,10]
l_after = [2,9,6,7,10,3,5,4,8,1]</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(seed (in "/dev/urandom" (rd 8)))
(for (N (length Lst) (>= N 2) (
(let I (rand 1
(xchg (nth Lst
(let L (range 1 15)
(println 'before L)
(knuth L)
(println 'after L) )</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
=={{header|PL/I}}==
===version 1===
<
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;</
===version 2===
<
/*--------------------------------------------------------------------
* 07.01.2014 Walter Pachl translated from REXX version 2
Line 1,792 ⟶ 3,873:
Put Edit(txt,(t(k) do k=1 To n))(Skip,a(7),10(f(3)));
End;
end;</
{{out}}
<pre>In 1 2 3 4 5 6 7 8 9 10
10 5 1 2 3 4 10 6 7 8 9 5
Line 1,807 ⟶ 3,888:
=={{header|PowerShell}}==
{{works with|PowerShell|3}}
<syntaxhighlight lang="powershell">$A = 1, 2, 3, 4, 5
Get-Random $A -Count $A.Count</syntaxhighlight>
{{works with|PowerShell|2}} <!-- Get-Random didn't exist in PowerShell 1 -->
<
$c = $a.Clone() # make copy to avoid clobbering $a
1..($c.Length - 1) | ForEach-Object {
Line 1,816 ⟶ 3,900:
}
$c[-1] # last value
}</
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.
=={{header|PureBasic}}==
<
Procedure KnuthShuffle(Array a(1))
Line 1,851 ⟶ 3,935:
KnuthShuffle(a())
Debug "shuffled: " + ArrayToString(a())</
{{out}}
<pre>shuffled: 1,8,6,0,5,9,2,4,7,3</pre>
=={{header|Python}}==
Python's standard library function <code>[http://docs.python.org/library/random.html#random.shuffle random.shuffle]</code> uses this algorithm and so should normally be used.
The function below is very similar:
<syntaxhighlight lang="python">from random import randrange
def knuth_shuffle(x):
Line 1,866 ⟶ 3,951:
x = list(range(10))
knuth_shuffle(x)
print("shuffled:", x)</
{{out}}
<pre>
shuffled: [5, 1, 6, 0, 8, 4, 2, 3, 9, 7]
</pre>
We could also write our own Knuth shuffle function as a fold, with a non-mutating swap function:
{{Works with|Python|3.7}}
<syntaxhighlight 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()</syntaxhighlight>
{{Out}}
<pre>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</pre>
=={{Header|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.)
<syntaxhighlight 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 ( [ --> [ )</syntaxhighlight>
{{out}}
Testing in the Quackery shell (REPL).
<pre>/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 ]
</pre>
Line 1,875 ⟶ 4,135:
See also, the built-in function 'sample'.
===Original Fisher-Yates version===
<
{
pool <- seq_len(n)
Line 1,887 ⟶ 4,147:
}
a
}</
===Knuth variation
<
{
a <- seq_len(n)
Line 1,909 ⟶ 4,169:
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"</
===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:
<syntaxhighlight 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"))</syntaxhighlight>
{{Out}}
<pre>> 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"</pre>
=={{header|Racket}}==
<syntaxhighlight lang="scheme">#lang racket
(define (swap! vec i j)
Line 1,925 ⟶ 4,221:
(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))</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|#21 "Seattle"}}
<syntaxhighlight lang="raku" line>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;
}</syntaxhighlight>
The shuffle is also built into the pick method on lists when you pass it a "whatever" for the number to pick:
<syntaxhighlight lang="raku" line>my @deck = @cards.pick(*);</syntaxhighlight>
=={{header|REBOL}}==
<
Title: "Fisher-Yates"
Purpose: {Fisher-Yates shuffling algorithm}
Line 1,950 ⟶ 4,258:
]
b
]</
=={{header|REXX}}==
===version 0, card pips===
<
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 .
if datatype(seed,'W') then call random ,,seed /*maybe use for RANDOM repeatability.*/
say '══════════════════ getting a new deck out of the box ···'
cards=2 /*now, there're 2 cards are in the deck*/
do j =1 for length(suit)
do k=1 for words(rank);
end /*k*/
end /*j*/
call
say; say '
do s=cards by -1 to 2; ?=random(1,s); parse value @.? @.s
end /*s*/
call
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
'''output'''
<pre
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
</pre>
===version 1, card names===
This version handles items with (leading/trailing/embedded) blanks in them, so '''parse''' isn't an option for shuffling.
<syntaxhighlight lang="rexx">/*REXX program shuffles a deck of playing cards (with jokers) using the Knuth shuffle.*/
suit = 'club spade diamond heart' /* " suit " " " */
say '══════════════════ getting a new deck out of the box ···'
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. */
end /*k*/
end /*j*/
call
say; say '
do s=cards by -1 to 2; ?=random(1,s); _=@.?; @.?=@.s; @.s=_
call show
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: parse arg
do m=1 for cards /* [↓] traipse through the card deck. */
if pos(break,@.m)\==0 then say /*show a blank to read cards easier. */
end /*m*/
return</syntaxhighlight>
'''output'''
<pre style="height:
card 1 ───► color joker
Line 2,039 ⟶ 4,345:
card 16 ───► spade ace
card 17 ───► spade
card 18 ───► spade trey
card 19 ───► spade 4
Line 2,053 ⟶ 4,359:
card 29 ───► diamond ace
card 30 ───► diamond
card 31 ───► diamond trey
card 32 ───► diamond 4
Line 2,067 ⟶ 4,373:
card 42 ───► heart ace
card 43 ───► heart
card 44 ───► heart trey
card 45 ───► heart 4
Line 2,080 ⟶ 4,386:
card 54 ───► heart king
card 1 ───►
card 2 ───►
card 3 ───►
card 4 ───► diamond
card 5 ───►
card 6 ───►
card 7 ───► club
card 8 ───► diamond
card 9 ───► diamond
card 10 ───►
card 11 ───►
card 12 ───►
card 13 ───► spade
card 14 ───► diamond
card 15 ───► diamond
card 16 ───►
card 17 ───►
card 18 ───►
card 19 ───►
card 20 ───► heart
card 21 ───► diamond
card 22 ───►
card 23 ───► club
card 24 ───► heart
card 25 ───► club
card 26 ───► diamond
card 27 ───►
card 28 ───►
card 29 ───► spade
card 30 ───► spade
card 31 ───► heart
card 32 ───► diamond
card 33 ───► diamond
card 34 ───►
card 35 ───► heart
card 36 ───► diamond
card 37 ───► diamond
card 38 ───► spade
card 39 ───►
card 40 ───► club
card 41 ───►
card 42 ───►
card 43 ───►
card 44 ───►
card 45 ───► heart
card 46 ───►
card 47 ───► diamond
card 48 ───►
card 49 ───► diamond
card 50 ───► club
card 51 ───►
card 52 ───► heart
card 53 ───►
card 54 ───►
</pre>
===version 2===
<
* 05.01.2014 Walter Pachl
* borrow one improvement from version 1
Line 2,161 ⟶ 4,467:
Do k=1 To n; ol=ol right(a.k,2); End
Say ol
Return</
{{out}}
<pre>In 1 2 3 4 5 6 7 8 9 10
10 2 1 10 3 4 5 6 7 8 9 2
Line 2,174 ⟶ 4,480:
2 1 10 7
Out 10 7 4 8 1 5 3 9 6 2</pre>
=={{header|Ring}}==
<syntaxhighlight 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
</syntaxhighlight>
<pre>
[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]
</pre>
=={{header|RPL}}==
Indexes of RPL lists and arrays start at 1.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
DUP SIZE 2 '''FOR''' j
j RAND * CEIL
GET LAST OVER j GET PUT j ROT PUT
-1 '''STEP'''
≫ '<span style="color:blue">KNUTH</span>' STO
|
<span style="color:blue">KNUTH</span> ''( {items} ➝ {items} )'' <span style="color:grey">// works also with [items]</span>
for j from last downto 2 do:
let k = random integer in range 1 ≤ k ≤ j
swap items[j] with items[k]
|}
=={{header|Ruby}}==
{{trans|Tcl}}
<
def knuth_shuffle!
j = length
Line 2,197 ⟶ 4,561:
end
r.keys.sort.each {|a| puts "#{a.inspect} => #{r[a]}"}</
results in
<pre>[1, 2, 3] => 16572
Line 2,205 ⟶ 4,569:
[3, 1, 2] => 16838
[3, 2, 1] => 16633</pre>
'''More
<
def knuth_shuffle!
(length - 1).downto(1) do |i|
Line 2,214 ⟶ 4,578:
self
end
end</
=={{header|Run BASIC}}==
<
for i = 1 to 52 ' make deck
cards(i) = i
Line 2,237 ⟶ 4,600:
if i mod 18 = 0 then print
next
print</
=={{header|Rust}}==
{{libheader|rand}}
<syntaxhighlight lang="rust">use rand::Rng;
extern crate rand;
fn knuth_shuffle<T>(v: &mut [T]) {
let mut rng = rand::
let l = v.len();
for n in
let i = rng.gen_range(0, l - n);
v.swap(i, l - n - 1);
Line 2,256 ⟶ 4,619:
fn main() {
let mut v: Vec<_> =
println!("before: {:?}", v);
knuth_shuffle(&mut v);
println!("after: {:?}", v);
}</
=={{header|Scala}}==
<
for (i <- 1 until a.size reverse) {
val j = util.Random nextInt (i + 1)
Line 2,274 ⟶ 4,635:
}
a
}</
=={{header|Scheme}}==
A functional version, using lists (inefficient), somewhat unusual in reversing the entire initial sublist on each pass instead of just swapping:
<syntaxhighlight 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))))))</syntaxhighlight>
A mutable version, using vectors (efficient):
<syntaxhighlight 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))))</syntaxhighlight>
=={{header|Scratch}}==
See Knuth's shuffle in action. Visit [https://scratch.mit.edu/projects/65352234/ this Scratch implementation] to see a demo and inspect its source.
=={{header|Seed7}}==
<
const type: intArray is array integer;
Line 2,308 ⟶ 4,717:
end for;
writeln;
end func;</
{{out}}
<pre>
7 5 6 8 3 10 9 4 2 1
</pre>
=={{header|SenseTalk}}==
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>
[8,9,7,3,4,5,1,2,6]
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program knuth_shuffle;
setrandom(0);
array := [1..10];
print("Before shuffling:", array);
shuffle(array);
print("After shuffling: ", array);
proc shuffle(rw tup);
loop for i in [1..#tup-1] do
j := random [i+1..#tup];
[tup(i), tup(j)] := [tup(j), tup(i)];
end loop;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>Before shuffling: [1 2 3 4 5 6 7 8 9 10]
After shuffling: [7 8 1 10 2 5 6 9 4 3]</pre>
=={{header|Sidef}}==
<syntaxhighlight 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))</syntaxhighlight>
{{out}}
<pre>
[7, 4, 3, 8, 9, 6, 10, 2, 1, 5]
</pre>
=={{header|Smalltalk}}==
{{works with|GNU Smalltalk}}
<
implemented (GNU Smalltalk version 3.0.4); so here it is an implementation"
SequenceableCollection extend [
Line 2,338 ⟶ 4,797:
]
]
].</
Testing
<
|c|
c := OrderedCollection new.
c addAll: #( 1 2 3 4 5 6 7 8 9 ).
Shuffler Knuth: c.
c display.</
=={{header|SNOBOL4}}==
<
-include 'Random.sno'
Line 2,377 ⟶ 4,836:
shuffle(a)
output = a2s(a)
end</
{{out}}
<pre>1 2 3 4 5 6 7 8 9 10 ->
2 10 4 9 1 5 6 8 7 3</pre>
=={{header|SparForte}}==
As a structured script.
<syntaxhighlight lang="ada">#!/usr/local/bin/spar
pragma annotate( summary, "shuffle" );
pragma annotate( description, "Implement the Knuth shuffle (aka the" );
pragma annotate( description, "Fisher-Yates-Durstenfeld shuffle)" );
pragma annotate( description, "for an integer array (or, if possible, an array of any" );
pragma annotate( description, "type). The Knuth shuffle is used to create a random" );
pragma annotate( description, "permutation of an array." );
pragma annotate( description, "Note: spar has a built-in arrays.shuffle() function that does this." );
pragma annotate( see_also, "http://rosettacode.org/wiki/Knuth_shuffle" );
pragma annotate( author, "Ken O. Burtch" );
pragma license( unrestricted );
pragma restriction( no_external_commands );
procedure shuffle is
subtype array_element_type is string;
type magic_items is array(1..3) of array_element_type;
a : magic_items := ( "bell", "book", "candle" );
t : array_element_type;
k : integer;
begin
for i in reverse arrays.first( a ) .. arrays.last( a )-1 loop
k := integer( numerics.rnd( i+1 ) ) - 1 + arrays.first(a);
t := a(i);
a(i) := a(k);
a(k) := t;
end loop;
for i in arrays.first( a ) .. arrays.last( a ) loop
? a(i);
end loop;
end shuffle;</syntaxhighlight>
{{out}}
<pre>
$ spar shuffle
bell
candle
book
$ spar shuffle
candle
bell
book</pre>
=={{header|Stata}}==
<syntaxhighlight 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</syntaxhighlight>
'''Output'''
<pre> 1 2 3 4 5 6 7 8 9 10
+---------------------------------------------------+
1 | 8 10 9 1 7 2 6 4 3 5 |
+---------------------------------------------------+</pre>
=={{header|Swift}}==
Version that works in Swift 5.x and probably above. This version works for any mutable bidirectional collection although O(n) time complexity can only be guaranteed for a RandomAccessCollection where the index meets the Apple requirements for O(1) access to elements.
Also has the advantage that it implemented the algorithm as written at the top of this page i.e. it counts down from the end and picks the random element from the part of the array that has not yet been traversed.
<syntaxhighlight lang="swift">extension BidirectionalCollection where Self: MutableCollection
{
mutating func shuffleInPlace()
{
var index = self.index(before: self.endIndex)
while index != self.startIndex
{
// Note the use of ... below. This makes the current element eligible for being selected
let randomInt = Int.random(in: 0 ... self.distance(from: startIndex, to: index))
let randomIndex = self.index(startIndex, offsetBy: randomInt)
self.swapAt(index, randomIndex)
index = self.index(before: index)
}
}
}
var a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a.shuffleInPlace()
print(a)
</syntaxhighlight>
{{out}}
<pre>[1, 5, 2, 7, 6, 0, 9, 8, 4, 3]</pre>
'''Simple version (any Swift version):''' Extend Array with shuffle methods; using arc4random_uniform from C stdlib:
<syntaxhighlight 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())</syntaxhighlight>
{{out}}
<pre>[8, 7, 2, 1, 6, 10, 5, 3, 4, 9]</pre>
'''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:
<syntaxhighlight 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]))</syntaxhighlight>
{{out}}
<pre>[2, 5, 7, 1, 6, 10, 4, 3, 8, 9]</pre>
{{works with|Swift | 2.0 }} 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:
<syntaxhighlight 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())</syntaxhighlight>
{{out}}
<pre>[3, 1, 5, 6, 7, 8, 10, 2, 4, 9]</pre>
=={{header|Tcl}}==
<
set j [llength $lst]
for {set i 0} {$j > 1} {incr i;incr j -1} {
Line 2,399 ⟶ 5,082:
5 2 1 4 3
% knuth_shuffle {tom dick harry peter paul mary}
tom paul mary harry peter dick</
As a test of skewing (an indicator of a poor implementation) this code was used:
<
foreach val [knuth_shuffle {1 2 3 4 5}] pos {pos0 pos1 pos2 pos3 pos4} {
incr tots($pos) $val
Line 2,411 ⟶ 5,094:
tots(pos2) = 299701
tots(pos3) = 299830
tots(pos4) = 300240</
=={{header|TI-83 BASIC}}==
Line 2,430 ⟶ 5,113:
:DelVar D
:Return
=={{header|Transd}}==
<syntaxhighlight lang="Scheme">#lang transd
MainModule: {
// Define an abstract type Vec to make the shuffling
// function polymorphic
Vec: typedef(Lambda<:Data Bool>(λ d :Data()
(starts-with (_META_type d) "Vector<"))),
kshuffle: (λ v Vec() locals: rnd 0
(for n in Range( (- (size v) 1) 0) do
(= rnd (randr (to-Int n)))
(with tmp (cp (get v n))
(set-el v n (get v rnd))
(set-el v rnd tmp))
)
(lout v)
),
_start: (λ
(with v [10,20,30,40,50,60,70,80,90,100]
(lout "Original:\n" v)
(lout "Shuffled:")
(kshuffle v))
(lout "")
(with v ["A","B","C","D","E","F","G","H"]
(lout "Original:\n" v)
(lout "Shuffled:")
(kshuffle (cp v))
// Transd has a built-in function that performs the same
// kind of random shuffle
(lout "Built-in shuffle:")
(lout (shuffle v)))
)
}</syntaxhighlight>
{{out}}
<pre>
Original:
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Shuffled:
[20, 60, 100, 80, 70, 10, 50, 90, 40, 30]
Original:
["A", "B", "C", "D", "E", "F", "G", "H"]
Shuffled:
["G", "A", "D", "B", "F", "E", "C", "H"]
Built-in shuffle:
["A", "E", "C", "H", "G", "F", "B", "D"]
</pre>
=={{header|TUSCRIPT}}==
<
oldnumbers=newnumbers="",range=20
LOOP nr=1,#range
Line 2,446 ⟶ 5,178:
ENDLOOP
PRINT "after ",newnumbers</
{{out}}
<pre>
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
</pre>
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">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</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Uiua}}==
{{works with|Uiua|0.10.0-dev.1}}
Build pairs of indexes to be swapped then apply these as a fold.
<syntaxhighlight lang="Uiua">
Knuth ← ∧(⍜⊏⇌)≡(⊟⌊×⚂.)⇌↘1⇡⧻.
Knuth ⇡10
</syntaxhighlight>
Typical output:
<pre>
[3 0 6 5 7 8 4 1 9 2]
</pre>
Line 2,456 ⟶ 5,229:
{{works with|ksh93}}
{{works with|pdksh}}
<
function shuffle {
integer i j t
Line 2,472 ⟶ 5,245:
done
}
# Test program.
set -A array 11 22 33 44 55 66 77 88 99 110
shuffle
echo "${array[@]}"</
=={{header|Ursala}}==
This function works on lists of any type and length, including character strings.
<
test program:
<
example = shuffle 'abcdefghijkl'</
{{out}}
<pre>'keacfjlbdigh'</pre>
=={{header|VBA}}==
<syntaxhighlight 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</syntaxhighlight>{{out}}<pre>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
</pre>
=={{header|VBScript}}==
;Implementation
<syntaxhighlight lang="vb">
function shuffle( a )
dim i
Line 2,510 ⟶ 5,345:
a = b
b = tmp
end sub</
;Invocation
<
a = array( 1,2,3,4,5,6,7,8,9)
wscript.echo "before: ", join( a, ", " )
Line 2,525 ⟶ 5,360:
wscript.echo "after: ", join( a, ", " )
shuffle a
wscript.echo "after: ", join( a, ", " )</
{{out}}
<pre>
before: 1, 2, 3, 4, 5, 6, 7, 8, 9
Line 2,542 ⟶ 5,377:
The output will be inserted in current edit buffer.
<
#90 = Time_Tick // seed for random number generator
#99 = 20 // number of items in the array
Line 2,583 ⟶ 5,418:
#93 = 0x7fffffff % 48271
#90 = (48271 * (#90 % #92) - #93 * (#90 / #92)) & 0x7fffffff
Return ((#90 & 0xffff) * #91 / 0x10000)</
{{out}}
<pre>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 </pre>
=={{header|V (Vlang)}}==
Updated to Vlang version 0.2.2
<syntaxhighlight 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')
}
</syntaxhighlight>
{{out}}
<pre>Input: [6, 9, 1, 4]
After Shuffle: [6, 1, 4, 9]
After Shuffle: [4, 9, 1, 6]
Output: [4, 9, 1, 6]</pre>
=={{header|Wren}}==
<syntaxhighlight lang="wren">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)")
}</syntaxhighlight>
{{out}}
Sample run:
<pre>
[] -> []
[10] -> [10]
[10, 20] -> [20, 10]
[10, 20, 30] -> [30, 10, 20]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">proc Shuffle(Array, Items, BytesPerItem);
int Array, Items, BytesPerItem;
int I, J;
char Temp(8);
[for I:= Items-1 downto 1 do
[J:= Ran(I+1); \range [0..I]
CopyMem(Temp, Array+I*BytesPerItem, BytesPerItem);
CopyMem(Array+I*BytesPerItem, Array+J*BytesPerItem, BytesPerItem);
CopyMem(Array+J*BytesPerItem, Temp, BytesPerItem);
];
];
string 0; \use zero-terminated strings
int A; char B; real C;
int I;
[A:= [1, 2, 3, 4, 5];
Shuffle(A, 5, 4 \bytes per int\);
for I:= 0 to 5-1 do
[IntOut(0, A(I)); ChOut(0, ^ )];
CrLf(0);
B:= "12345";
Shuffle(B, 5, 1 \byte per char\);
for I:= 0 to 5-1 do
[ChOut(0, B(I)); ChOut(0, ^ )];
CrLf(0);
C:= [1., 2., 3., 4., 5.];
Shuffle(addr C(0), 5, 8 \bytes per real\);
for I:= 0 to 5-1 do
[RlOut(0, C(I)); ChOut(0, ^ )];
CrLf(0);
A:= [10];
Shuffle(A, 1, 4 \bytes per int\);
for I:= 0 to 1-1 do
[IntOut(0, A(I)); ChOut(0, ^ )];
CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
2 4 1 5 3
1 3 4 5 2
5.00000 4.00000 2.00000 1.00000 3.00000
10
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">// Rosetta Code problem: https://www.rosettacode.org/wiki/Ramsey%27s_theorem
// by Jjuanhdez, 06/2022
dim array(52)
for i = 1 to arraysize(array(),1) : array(i) = i : next i
print "Starting array"
for i = 1 to arraysize(array(),1)
print array(i) using "####";
next i
KnuthShuffle(array())
print "\n\nAfter Knuth shuffle downwards"
for i = 1 to arraysize(array(),1)
print array(i) using "####";
next i
print
end
sub KnuthShuffle(a())
local i, j, t, lb, ub
lb = 1
ub = arraysize(a(),1) - lb
for i = lb to ub
j = round(ran(i +1))
t = a(lb + i)
a(lb + i) = a(lb + j)
a(lb + j) = t
next i
end sub</syntaxhighlight>
=={{header|zkl}}==
Two versions, imperative and functional, same results.
xs has to be a mutable list.
<syntaxhighlight 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
}</syntaxhighlight>
<pre>
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")
</pre>
|