Knuth shuffle: Difference between revisions
PascalABC.NET
m (→{{header|Joy}}) |
(PascalABC.NET) |
||
(34 intermediate revisions by 18 users not shown) | |||
Line 53:
{{trans|Python}}
<
L(i) (x.len - 1 .< 0).step(-1)
V j = random:(0..i)
Line 60:
V x = Array(0..9)
knuth_shuffle(&x)
print(‘shuffled: ’x)</
{{out}}
Line 69:
=={{header|360 Assembly}}==
{{trans|BBC BASIC}}
<
* Knuth shuffle 02/11/2015
KNUTHSH CSECT
Line 119:
YREGS
END KNUTHSH
</syntaxhighlight>
{{out}}
<pre>
Line 129:
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.
<
define tempMask $ff
define range $00
Line 197:
end:
brk</
=={{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 */
Line 343:
/* 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 369:
array
(1- (first (dimensions name array)))
state))</
=={{header|Action!}}==
<
BYTE i
Line 414:
PrintE("Shuffled data:")
PrintTable(tab,size)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Knuth_shuffle.png Screenshot from Atari 8-bit computer]
Line 427:
=={{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 448:
List(K) := T;
end loop;
end Generic_Shuffle;</
An example using Generic_Shuffle.
<
with Generic_Shuffle;
Line 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)
{
Line 488:
}
}
}</
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G}}
<
(
ENTIER (random * ABS (b-a+1) + (a<b|a|b))
Line 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}}==
Line 517 ⟶ 545:
===Iteration===
<
set array to {}
Line 530 ⟶ 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:
<
on shuffle(theList, l, r)
set listLength to (count theList)
Line 561 ⟶ 589:
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)</
{{output}}
''eg.''
<
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:
<
use framework "Foundation"
use framework "GameplayKit"
Line 591 ⟶ 619:
return theList
end shuffle</
----
===Functional composition===
<
-- knuthShuffle :: [a] -> [a]
Line 667 ⟶ 695:
end script
end if
end mReturn</
{{Out}}
e.g.
<
"iota", "kappa", "lambda", "epsilon", "beta", "eta"}</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
Line 908 ⟶ 936:
</syntaxhighlight>
=={{header|Arturo}}==
<
if 0=size arr -> return []
Line 928 ⟶ 956:
print knuth [10]
print knuth [10 20]
print knuth [10 20 30]</
=={{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 944 ⟶ 972:
s .= "," . a%A_Index%
Return SubStr(s,2) ; drop leading comma
}</
For Arrays:
Line 951 ⟶ 979:
[https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array#6274381 (translated from)]
<
shuffled:=shuffle(toShuffle)
;p(toShuffle) ;because it modifies the original array
Line 967 ⟶ 995:
}
return a
}</
=={{header|AutoIt}}==
<syntaxhighlight lang="autoit">
Dim $a[10]
ConsoleWrite('array before permutation:' & @CRLF)
Line 996 ⟶ 1,024:
Next
EndFunc
</syntaxhighlight>
{{out}}
Line 1,010 ⟶ 1,038:
This example shows how to shuffle such arrays.
The elements can be integers, floating-point numbers, or strings.
<
function shuffle(array, len, i, j, t) {
for (i = len; i > 1; i--) {
Line 1,030 ⟶ 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 1,053 ⟶ 1,081:
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT
PRINT</
{{out}}
Line 1,067 ⟶ 1,095:
==={{header|Applesoft BASIC}}===
As mentioned in the Sinclair ZX81 BASIC solution, for very small positive integer values, a string is a much more memory-efficient array, but here is an example of an array with numbers. Line <code>150</code> initializes and prints each element in the array. Line <code>190</code> performs the swap of the elements.
<
110 REM KNUTH SHUFFLE
120 :
Line 1,079 ⟶ 1,107:
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
Line 1,089 ⟶ 1,116:
==={{header|BBC BASIC}}===
<
DIM pack%(cards%)
FOR I% = 1 TO cards%
Line 1,100 ⟶ 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}}===
<
110 RANDOMIZE
120 NUMERIC ARRAY(1 TO 20)
Line 1,126 ⟶ 1,181:
310 IF CARD<>I THEN LET T=A(CARD):LET A(CARD)=A(I):LET A(I)=T
320 NEXT
330 END DEF</
==={{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
Line 1,139 ⟶ 1,219:
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
<
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
Line 1,169 ⟶ 1,248:
IF d(i) = i THEN PRINT -d(i); ELSE PRINT d(i);
NEXT
WEND: PRINT: PRINT " = "; k, TIMER-z: END</
==={{header|Sinclair ZX81 BASIC}}===
Line 1,175 ⟶ 1,254:
The program works with the unexpanded (1k RAM) ZX81.
<
20 LET A$=""
30 FOR I=1 TO 26
Line 1,188 ⟶ 1,267:
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</
{{out}}
While the program is running, we will see something like this (using lower case as a stand-in for inverse video):
Line 1,197 ⟶ 1,276:
==={{header|True BASIC}}===
{{trans|BASIC}}
<
RANDOMIZE
Line 1,222 ⟶ 1,301:
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT L0
END</
{{out}}
<pre>Same as BASIC entry.</pre>
Line 1,231 ⟶ 1,310:
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 1,274 ⟶ 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
Line 1,283 ⟶ 1,362:
BQN's arrays are immutable, but variable values can be changed using the `↩` symbol. This program repeatedly changes the array's value using under.
<
𝕊 arr:
l ← ≠arr
Line 1,296 ⟶ 1,375:
P ⟨10⟩
P ⟨10, 20⟩
P ⟨10, 20, 30⟩</
[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 1,312 ⟶ 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 1,336 ⟶ 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 1,389 ⟶ 1,468:
printf(" %d", x[i]);
return 0;
}</
=={{header|C sharp|C#}}==
<
{
System.Random random = new System.Random();
Line 1,400 ⟶ 1,479:
T temp = array[i]; array[i] = array[j]; array[j] = temp;
}
}</
=={{header|C++}}==
'''Compiler:''' [[g++]] (version 4.3.2 20081105 (Red Hat 4.3.2-7))
<
#include <algorithm>
#include <iterator>
Line 1,410 ⟶ 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 1,416 ⟶ 1,498:
}
}
}</
The standard library provides this in the form of <code>std::random_shuffle</code>.
<
#include <vector>
Line 1,428 ⟶ 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|CLU}}==
<
lo: int := array[T]$low(a)
hi: int := array[T]$high(a)
Line 1,458 ⟶ 1,540:
stream$puts(po, int$unparse(i) || " ")
end
end start_up</
{{out}}
<pre>7 9 2 3 4 8 1 6 5</pre>
Line 1,464 ⟶ 1,546:
=={{header|CMake}}==
<
# stores the result in a list.
function(shuffle var)
Line 1,496 ⟶ 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}}==
<
PROGRAM-ID. knuth-shuffle.
Line 1,532 ⟶ 1,614:
GOBACK
.</
=={{header|CoffeeScript}}==
{{trans|JavaScript}}
<
n = a.length
while n > 1
Line 1,556 ⟶ 1,638:
for key, val of counts
console.log "#{key}: #{val}"</
{{out}}
<pre>
Line 1,569 ⟶ 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 1,590 ⟶ 1,672:
do (rotatef (aref array (random i))
(aref array (1- i)))
finally (return array)))</
=={{header|Crystal}}==
<
i = items.size-1
while i > 1
Line 1,601 ⟶ 1,683:
i -= 1
end
end</
=={{header|D}}==
===Standard Version===
A variant of the Knuth shuffle is in the D standard library Phobos:
<
import std.stdio, std.random;
Line 1,612 ⟶ 1,694:
a.randomShuffle;
a.writeln;
}</
{{out}}
<pre>[8, 9, 3, 1, 7, 5, 4, 6, 2]</pre>
Line 1,618 ⟶ 1,700:
===One Implementation===
This shuffles any collection that supports random access, length and swapping of items:
<
void knuthShuffle(Range)(Range r)
Line 1,631 ⟶ 1,713:
a.knuthShuffle;
a.writeln;
}</
=={{header|Delphi}}==
Line 1,637 ⟶ 1,719:
=={{header|DWScript}}==
<
var
i, j, tmp : Integer;
Line 1,645 ⟶ 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 1,656 ⟶ 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
swap a[r] a[i]
.
.
arr[] = [ 1 2 3 ]
print arr[]
</syntaxhighlight>
=={{header|EchoLisp}}==
<
Remark- The native '''shuffle''' function implementation in EchoLisp has been replaced by this one.
Thx Rosetta Code.
Line 1,707 ⟶ 1,790:
'(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"
Line 1,728 ⟶ 1,811:
def main = shuffle (fromto 1 9)
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,788 ⟶ 1,871:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,796 ⟶ 1,879:
=={{header|Elena}}==
ELENA
<
import extensions;
Line 1,808 ⟶ 1,891:
var max := self.Length;
for(int i := 0
{
var j := randomGenerator.
self.exchange(i,j)
Line 1,821 ⟶ 1,904:
public program()
{
var a := Array.allocate
console.printLine(a.randomize())
}</
{{out}}
<pre>
</pre>
=={{header|Elixir}}==
{{trans|Erlang}}
<
def shuffle( inputs ) do
n = length( inputs )
Line 1,853 ⟶ 1,936:
Map.update(acc, k, 1, &(&1+1))
end)
|> Enum.each(fn {k,v} -> IO.inspect {k,v} end)</
{{out}}
Line 1,867 ⟶ 1,950:
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module( knuth_shuffle ).
Line 1,882 ⟶ 1,965:
Item = lists:nth( random:uniform(N), Inputs ),
{lists:delete(Item, Inputs), [Item | Acc]}.
</syntaxhighlight>
{{out}}
<pre>
Line 1,890 ⟶ 1,973:
=={{header|ERRE}}==
<
CONST CARDS%=52
Line 1,909 ⟶ 1,992:
PRINT
END PROGRAM
</syntaxhighlight>
=={{header|Euphoria}}==
{{trans|BASIC}}
<
cards = repeat(0,52)
integer card,temp
Line 1,935 ⟶ 2,018:
for i = 1 to 52 do
printf(1,"%d ",cards[i])
end for</
=={{header|F_Sharp|F#}}==
Line 1,941 ⟶ 2,024:
This is the original Fisher-Yates shuffle as described by the link:
<
let FisherYatesShuffle (initialList : array<'a>) = // '
Line 1,957 ⟶ 2,040:
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</
Here's the modified Knuth shuffle which shuffles the original array in place
<
let Swap i j = // Standard swap
let item = lst.[i]
Line 1,968 ⟶ 2,051:
[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</
Example:
<
val it : string array = [|"Marvin"; "Doug"; "Sam"; "Darrell"; "Ken"; "Greg"|]</
=={{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 2,002 ⟶ 2,085:
echo (b)
}
}</
=={{header|Forth}}==
<
: shuffle ( deck size -- )
Line 2,019 ⟶ 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 2,055 ⟶ 2,138:
end subroutine Shuffle
end program Knuth_Shuffle</
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Line 2,134 ⟶ 2,217:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Starting array
Line 2,154 ⟶ 2,237:
=={{header|Frink}}==
The built-in method <CODE><I>array</I>.shuffle[]</CODE> implements the Fisher-Yates-Knuth shuffle algorithm:
<
a = [1,2,3]
a.shuffle[]
</syntaxhighlight>
=={{header|FunL}}==
<
res = array( a )
n = a.length()
Line 2,168 ⟶ 2,251:
res(i), res(r) = res(r), res(i)
res.toList()</
=={{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]'''
<
Dim iTotal As Integer = 40
Dim iCount, iRand1, iRand2 As Integer
Line 2,197 ⟶ 2,325:
Next
End</
Output:
<pre>
Line 2,205 ⟶ 2,333:
=={{header|GAP}}==
<
ShuffleAlt := function(a)
local i, j, n, t;
Line 2,230 ⟶ 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}}==
Line 2,238 ⟶ 2,366:
implementing a Fisher–Yates shuffle.)
<
import (
Line 2,259 ⟶ 2,387:
}
fmt.Println(a)
}</
To shuffle any type:
<
import (
Line 2,308 ⟶ 2,436:
shuffle(a)
fmt.Println(a)
}</
{{out|Example output}} (of either program)
<pre>
Line 2,317 ⟶ 2,445:
=={{header|Groovy}}==
Solution:
<
if (list == null || list.empty) return list
def r = new Random()
Line 2,326 ⟶ 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]
Line 2,340 ⟶ 2,468:
=={{header|Haskell}}==
<
mkRands :: Int -> IO [Int]
Line 2,356 ⟶ 2,484:
knuthShuffle :: [a] -> IO [a]
knuthShuffle xs = (foldr swapElems xs . zip [1 ..]) <$> mkRands (length xs)</
or, as an alternative to making two indexed references into the list with '''(!!)''':
<
import Data.Bool (bool)
Line 2,380 ⟶ 2,508:
main :: IO ()
main = knuthShuffle ['a' .. 'k'] >>= print</
Examples of use of either of the two versions above:
Line 2,389 ⟶ 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)</
{{out}} Detailed example:
<pre>*Main> knuthShuffleProcess ['a'..'k']
Line 2,406 ⟶ 2,534:
"iebjhkcgfad"</pre>
An imperative implementation using arrays and the <code>ST</code> monad:
<
import Data.STRef
import Control.Monad
Line 2,426 ⟶ 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 2,443 ⟶ 2,571:
every writes(!A," ")
write()
end</
{{out}}
<pre>->ks
Line 2,450 ⟶ 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 2,481 ⟶ 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 2,493 ⟶ 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 2,520 ⟶ 2,647:
11 2 3
0 11 2</
<
11 2 3
0 11 2
Line 2,532 ⟶ 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 2,564 ⟶ 2,691:
+----+---+--+---+
|cC%$|bbB|aA|dD@|
+----+---+--+---+</
=={{header|Java}}==
<
public static final Random gen = new Random();
Line 2,590 ⟶ 2,717:
array[k] = temp;
}
}</
=={{header|JavaScript}}==
Line 2,596 ⟶ 2,723:
===ES5===
<
var rand, temp, i;
for (i = arr.length - 1; i > 0; i -= 1) {
rand = Math.floor((i + 1) * Math.random());//get random between zero and i (inclusive)
temp = arr[rand];
arr[rand] = arr[i]; //swap i (last element) with random element.
arr[i] = temp;
}
Line 2,620 ⟶ 2,747:
for (var key in res) {
print(key + "\t" + res[key]);
}</
Results in:
<pre>1,2,3 16619
Line 2,628 ⟶ 2,755:
3,1,2 16460
3,2,1 16596</pre>
===ES6===
====Mutating in-place swap====
<
// knuthShuffle :: [a] -> [a]
Line 2,679 ⟶ 2,805:
return test();
})();
</syntaxhighlight>
{{Out}}
e.g.
<
"lambda", "eta", "zeta", "beta", "mu", "alpha"]</
====Non-mutating swap====
<
// knuthShuffle :: [a] -> [a]
Line 2,747 ⟶ 2,873:
// MAIN ---
return test();
})();</
{{Out}}
e.g.
<
"kappa", "alpha", "gamma", "lambda", "zeta", "iota"]</
=={{header|Joy}}==
<syntaxhighlight lang=
(* Take the size of the array (without destroying it) *)
dup dup size
Line 2,767 ⟶ 2,893:
[second] map.</syntaxhighlight>
Using knuth-shuffle (file shuffle.joy):
<syntaxhighlight lang=
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
knuth-shuffle.</syntaxhighlight>
Line 2,793 ⟶ 2,919:
where program.jq is the following program:
<syntaxhighlight lang="jq">
# 52-card deck:
def deck:
Line 2,837 ⟶ 2,963:
task,
(deck|knuthShuffle | nwise(13) | implode)
</syntaxhighlight>
{{out}}
<pre>
Line 2,854 ⟶ 2,980:
{{works with|Julia|0.6}}
<
for i in length(v):-1:2
j = rand(r, 1:i)
Line 2,864 ⟶ 2,990:
v = collect(1:20)
println("# v = $v\n -> ", knuthshuffle!(v))</
{{out}}
Line 2,871 ⟶ 2,997:
=={{header|Kotlin}}==
<
internal val gen = java.util.Random()
}
Line 2,901 ⟶ 3,027:
require(s.toSortedSet() == ia.toSet())
}
}</
{{out}}
<pre>xdhsvtnumjgbywiqoapcelkrfz
Line 2,930 ⟶ 3,056:
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def shuffle
Line 2,960 ⟶ 3,086:
{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 2,982 ⟶ 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 3,008 ⟶ 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 3,022 ⟶ 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 3,060 ⟶ 3,186:
make "a ( list 1 2 3 4 5 6 7 8 9 10 )
make "a shuffle :a
show :a</
=={{header|Lua}}==
<
for n = #t, 1, -1 do
local k = math.random(n)
Line 3,075 ⟶ 3,201:
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 {
Line 3,089 ⟶ 3,215:
}
</syntaxhighlight>
=={{header|M4}}==
<
define(`randSeed',141592653)
define(`rand_t',`eval(randSeed^(randSeed>>13))')
Line 3,118 ⟶ 3,244:
show(`b')
shuffle(`b')
show(`b')</
{{out}}
<pre>
Line 3,132 ⟶ 3,258:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Usage of built-in function:
<
Custom function:
<
Module[{indices = {}, allindices = Range[Length[input]]},
Do[
Line 3,143 ⟶ 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 3,158 ⟶ 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.
<
list = list( randperm(numel(list)) );
end</
=={{header|Maxima}}==
<
random_permutation([a, b, c]);</
=={{header|Modula-3}}==
<
IMPORT IO, Fmt, Random;
Line 3,202 ⟶ 3,328:
END;
IO.Put("\n");
END Shuffle.</
{{out}}
<pre>
Line 3,212 ⟶ 3,338:
=={{header|MUMPS}}==
<
Set list="",n=0
Set ii="" For Set ii=$Order(items(ii)) Quit:ii="" Do
Line 3,295 ⟶ 3,421:
Queen of Spades
King of Diamonds
5 of Clubs</
=={{header|Nemerle}}==
<
{
def rnd = Random();
Line 3,305 ⟶ 3,431:
arr[i] <-> arr[(rnd.Next(i, arr.Length))];
arr
}</
=={{header|NetRexx}}==
===version 1===
<
options replace format comments java crossref savelog symbols nobinary
Line 3,357 ⟶ 3,483:
say
return</
{{out}}
<pre>
Line 3,372 ⟶ 3,498:
===version 2===
<
* 08.01.2014 Walter Pachl modified to show state development a la Rexx
*--------------------------------------------------------------------*/
Line 3,405 ⟶ 3,531:
method showHand(deck = ArrayList,tag=REXX) public static binary
say tag ArrayList(deck.subList(0,deck.size)).toString
return</
{{out}}
<pre>In [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Line 3,421 ⟶ 3,547:
=={{header|Nim}}==
Note that the function "shuffle" exists in the standard module "random" and that it uses the Knuth shuffle.
<
randomize()
Line 3,431 ⟶ 3,557:
var x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
shuffle(x)
echo x</
=={{header|Objective-C}}==
<
@interface NSMutableArray (KnuthShuffle)
Line 3,455 ⟶ 3,581:
}
return 0;
}</
{{out}}
<pre>
Line 3,473 ⟶ 3,599:
=={{header|OCaml}}==
<
for n = Array.length arr - 1 downto 1 do
let k = Random.int (n + 1) in
Line 3,479 ⟶ 3,605:
arr.(n) <- arr.(k);
arr.(k) <- temp
done</
=={{header|Oforth}}==
Line 3,486 ⟶ 3,612:
Returns a new list
<
| s i l |
self asListBuffer ->l
self size dup ->s 1- loop: i [ s i - rand i + i l swapValues ]
l dup freeze ; </
=={{header|Ol}}==
Line 3,497 ⟶ 3,623:
Ol is functional language, so we should make a copy of shuffling tuple and return this shuffled copy.
<
(define (shuffle tp)
(let ((items (vm:cast tp (type tp)))) ; make a copy
Line 3,513 ⟶ 3,639:
(tuple->list
(shuffle (list->tuple (iota (length tp)))))))
</syntaxhighlight>
Testing:
<
(define items (tuple 1 2 3 4 5 6 7 8 9))
(print "tuple before: " items)
Line 3,524 ⟶ 3,650:
(print "list before: " items)
(print "list after: " (list-shuffle items))
</syntaxhighlight>
Output:
<pre>
Line 3,534 ⟶ 3,660:
=={{header|Oz}}==
<
proc {Shuffle Arr}
Low = {Array.low Arr}
Line 3,552 ⟶ 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 3,564 ⟶ 3,690:
};
FY(vector(52,i,i))</
=={{header|Pascal}}==
<
const
Line 3,618 ⟶ 3,744:
DisplayList(a);
end;
end.</
{{out}}
<pre> -5 -4 -3 -2 -1 0 1 2 3 4 5
Line 3,627 ⟶ 3,753:
-4 1 -1 -5 5 2 0 3 -2 -3 4
-3 -5 4 2 -4 0 5 3 1 -1 -2</pre>
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
procedure Shuffle<T>(a: array of T);
begin
for var i := a.Length - 1 downto 1 do
Swap(a[i], a[Random(i + 1)]);
end;
begin
var a := Arr(1..9);
Shuffle(a);
a.Print;
end.
</syntaxhighlight>
{{out}}
<pre>
5 8 6 1 3 4 2 9 7
</pre>
=={{header|Perl}}==
<
my @a = @_;
foreach my $n (1 .. $#a) {
Line 3,636 ⟶ 3,781:
}
return @a;
}</
=={{header|Phix}}==
<!--<
<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>
Line 3,648 ⟶ 3,793:
<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>
<!--</
{{out}}
<pre style="font-size: 12px">
Line 3,657 ⟶ 3,802:
=={{header|PHP}}==
<
function yates_shuffle($arr){
$shuffled = Array();
Line 3,674 ⟶ 3,819:
list($arr[$i], $arr[$rnd]) = array($arr[$rnd], $arr[$i]);
}
}</
=={{header|Picat}}==
<
_ = random2(),
L = 1..10,
Line 3,691 ⟶ 3,836:
L[I] := L[J],
L[J] := Tmp
end.</
{{out}}
Line 3,698 ⟶ 3,843:
=={{header|PicoLisp}}==
<
(de knuth (Lst)
Line 3,708 ⟶ 3,853:
(println 'before L)
(knuth L)
(println 'after L) )</
{{out}}
<pre>
Line 3,717 ⟶ 3,862:
=={{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 3,747 ⟶ 3,892:
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
Line 3,763 ⟶ 3,908:
=={{header|PowerShell}}==
{{works with|PowerShell|3}}
<
Get-Random $A -Count $A.Count</
{{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 3,774 ⟶ 3,919:
}
$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 3,809 ⟶ 3,954:
KnuthShuffle(a())
Debug "shuffled: " + ArrayToString(a())</
{{out}}
<pre>shuffled: 1,8,6,0,5,9,2,4,7,3</pre>
Line 3,816 ⟶ 3,961:
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:
<
def knuth_shuffle(x):
Line 3,825 ⟶ 3,970:
x = list(range(10))
knuth_shuffle(x)
print("shuffled:", x)</
{{out}}
<pre>
Line 3,834 ⟶ 3,979:
We could also write our own Knuth shuffle function as a fold, with a non-mutating swap function:
{{Works with|Python|3.7}}
<
from functools import reduce
Line 3,928 ⟶ 4,073:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Repeated Knuth shuffles of ['a' .. 'k']:
Line 3,948 ⟶ 4,093:
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.)
<
[ dup size random pluck
nested rot join swap ]
Line 3,968 ⟶ 4,113:
[ dup size 1 - times
[ i 1+ dup 1+ random
rot [exch] ] ] is knuffle ( [ --> [ )</
{{out}}
Line 4,010 ⟶ 4,155:
===Original Fisher-Yates version===
<
{
pool <- seq_len(n)
Line 4,021 ⟶ 4,166:
}
a
}</
===Knuth variation===
<
{
a <- seq_len(n)
Line 4,043 ⟶ 4,188:
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:
<
{
last <- length(vec)
Line 4,064 ⟶ 4,209:
replicate(10, knuth(c(10, 20)))
replicate(10, knuth(c(10, 20, 30)))
knuth(c("Also", "works", "for", "strings"))</
{{Out}}
<pre>> knuth(integer(0))
Line 4,084 ⟶ 4,229:
=={{header|Racket}}==
<
(define (swap! vec i j)
Line 4,099 ⟶ 4,244:
x)))
(knuth-shuffle '(1 2 3 4))</
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|#21 "Seattle"}}
<syntaxhighlight lang="raku"
for 1 ..^ @a -> $n {
my $k = (0 .. $n).pick;
Line 4,110 ⟶ 4,255:
}
return @a;
}</
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"
=={{header|REBOL}}==
<
Title: "Fisher-Yates"
Purpose: {Fisher-Yates shuffling algorithm}
Line 4,132 ⟶ 4,277:
]
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 " " " " " */
Line 4,158 ⟶ 4,303:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: _=; do m=1 for cards; _=_ @.m; end /*m*/; say _; return</
'''output'''
<pre>
Line 4,170 ⟶ 4,315:
===version 1, card names===
This version handles items with (leading/trailing/embedded) blanks in them, so '''parse''' isn't an option for shuffling.
<
rank = 'ace deuce trey 4 5 6 7 8 9 10 jack queen king' /*use pip names for cards*/
suit = 'club spade diamond heart' /* " suit " " " */
Line 4,196 ⟶ 4,341:
say 'card' right(m, 2) '───►' @.m /*display a particular card from deck. */
end /*m*/
return</
'''output'''
<pre style="height:50ex">
Line 4,319 ⟶ 4,464:
===version 2===
<
* 05.01.2014 Walter Pachl
* borrow one improvement from version 1
Line 4,341 ⟶ 4,486:
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
Line 4,356 ⟶ 4,501:
=={{header|Ring}}==
<
# Project : Knuth shuffle
Line 4,385 ⟶ 4,530:
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 4,412 ⟶ 4,580:
end
r.keys.sort.each {|a| puts "#{a.inspect} => #{r[a]}"}</
results in
<pre>[1, 2, 3] => 16572
Line 4,421 ⟶ 4,589:
[3, 2, 1] => 16633</pre>
'''More idiomatic:'''
<
def knuth_shuffle!
(length - 1).downto(1) do |i|
Line 4,429 ⟶ 4,597:
self
end
end</
=={{header|Run BASIC}}==
<
for i = 1 to 52 ' make deck
cards(i) = i
Line 4,451 ⟶ 4,619:
if i mod 18 = 0 then print
next
print</
=={{header|Rust}}==
{{libheader|rand}}
<
extern crate rand;
Line 4,475 ⟶ 4,643:
knuth_shuffle(&mut v);
println!("after: {:?}", v);
}</
=={{header|Scala}}==
<
for (i <- 1 until a.size reverse) {
val j = util.Random nextInt (i + 1)
Line 4,486 ⟶ 4,654:
}
a
}</
=={{header|Scheme}}==
A functional version, using lists (inefficient), somewhat unusual in reversing the entire initial sublist on each pass instead of just swapping:
<
(import (rnrs base (6))
(srfi :27 random-bits))
Line 4,507 ⟶ 4,675:
(let
((li-prime (semireverse li (random-integer (length li)))))
(cons (car li-prime) (shuffle (cdr li-prime))))))</
A mutable version, using vectors (efficient):
<
(import (rnrs base (6))
(srfi :27 random-bits))
Line 4,531 ⟶ 4,699:
((j (random-integer i)))
(vector-swap! vec (- i 1) j)))
(countdown (vector-length vec))))</
=={{header|Scratch}}==
Line 4,537 ⟶ 4,705:
=={{header|Seed7}}==
<
const type: intArray is array integer;
Line 4,568 ⟶ 4,736:
end for;
writeln;
end func;</
{{out}}
Line 4,576 ⟶ 4,744:
=={{header|SenseTalk}}==
<
set last to the number of items in list
Line 4,584 ⟶ 4,752:
end repeat
put list</
{{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}}==
<
for i (a.len ^.. 1) {
var j = i.irand
Line 4,599 ⟶ 4,787:
}
say knuth_shuffle(@(1..10))</
{{out}}
<pre>
Line 4,607 ⟶ 4,795:
=={{header|Smalltalk}}==
{{works with|GNU Smalltalk}}
<
implemented (GNU Smalltalk version 3.0.4); so here it is an implementation"
SequenceableCollection extend [
Line 4,628 ⟶ 4,816:
]
]
].</
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 4,667 ⟶ 4,855:
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}}==
<
function shuffle(a) {
n = length(a)
Line 4,688 ⟶ 4,927:
shuffle(1..10)
end</
'''Output'''
Line 4,698 ⟶ 4,937:
=={{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:
<
extension Array {
Line 4,720 ⟶ 4,986:
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())</
{{out}}
Line 4,727 ⟶ 4,993:
'''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:
<
func shuffleInPlace<T: MutableCollectionType where T.Index: RandomAccessIndexType>(inout collection: T) {
Line 4,757 ⟶ 5,023:
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]))</
{{out}}
Line 4,764 ⟶ 5,030:
{{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:
<
// Define a protocol for shuffling:
Line 4,813 ⟶ 5,079:
{ /* Implementation provided by Shufflable protocol extension */ }
print([1, 2, 3, 4, 5, 6, 7, 8, 9, 10].shuffle())</
{{out}}
Line 4,819 ⟶ 5,085:
=={{header|Tcl}}==
<
set j [llength $lst]
for {set i 0} {$j > 1} {incr i;incr j -1} {
Line 4,835 ⟶ 5,101:
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 4,847 ⟶ 5,113:
tots(pos2) = 299701
tots(pos3) = 299830
tots(pos4) = 300240</
=={{header|TI-83 BASIC}}==
Line 4,866 ⟶ 5,132:
: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 4,882 ⟶ 5,197:
ENDLOOP
PRINT "after ",newnumbers</
{{out}}
<pre>
Line 4,890 ⟶ 5,205:
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">PRINT "before:"
FOR L = 0 TO 51
@(L) = L
Line 4,911 ⟶ 5,226:
END
100 @(POP()) = POP() : @(POP()) = POP() : RETURN</
{{out}}
<pre>before:
Line 4,917 ⟶ 5,232:
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>
=={{header|UNIX Shell}}==
{{works with|ksh93}}
{{works with|pdksh}}
<
function shuffle {
integer i j t
Line 4,941 ⟶ 5,268:
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}}==
<
Dim t As Variant, i As Integer
If Not IsMissing(a) Then
Line 5,002 ⟶ 5,329:
Debug.Print "After: ";
For Each i In f: Debug.Print i;: Next i: Debug.Print
End Sub</
After:
Before: 10
Line 5,018 ⟶ 5,345:
=={{header|VBScript}}==
;Implementation
<syntaxhighlight lang="vb">
function shuffle( a )
dim i
Line 5,037 ⟶ 5,364:
a = b
b = tmp
end sub</
;Invocation
<
a = array( 1,2,3,4,5,6,7,8,9)
wscript.echo "before: ", join( a, ", " )
Line 5,052 ⟶ 5,379:
wscript.echo "after: ", join( a, ", " )
shuffle a
wscript.echo "after: ", join( a, ", " )</
{{out}}
<pre>
Line 5,069 ⟶ 5,396:
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 5,110 ⟶ 5,437:
#93 = 0x7fffffff % 48271
#90 = (48271 * (#90 % #92) - #93 * (#90 / #92)) & 0x7fffffff
Return ((#90 & 0xffff) * #91 / 0x10000)</
{{out}}
<pre>Before:
Line 5,117 ⟶ 5,444:
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
<
import rand.seed
Line 5,139 ⟶ 5,466:
println('Output: $arr')
}
</syntaxhighlight>
{{out}}
<pre>Input: [6, 9, 1, 4]
Line 5,147 ⟶ 5,474:
=={{header|Wren}}==
<
var rand = Random.new()
Line 5,167 ⟶ 5,494:
knuthShuffle.call(a)
System.print("%(b) -> %(a)")
}</
{{out}}
Line 5,179 ⟶ 5,506:
=={{header|XPL0}}==
<
int Array, Items, BytesPerItem;
int I, J;
Line 5,214 ⟶ 5,541:
[IntOut(0, A(I)); ChOut(0, ^ )];
CrLf(0);
]</
{{out}}
Line 5,225 ⟶ 5,552:
=={{header|Yabasic}}==
<
// by Jjuanhdez, 06/2022
Line 5,256 ⟶ 5,583:
a(lb + j) = t
next i
end sub</
=={{header|zkl}}==
Two versions, imperative and functional, same results.
xs has to be a mutable list.
<
foreach i in ([xs.len()-1..1,-1]){ xs.swap(i,(0).random(0,i+1)) }
xs
Line 5,268 ⟶ 5,595:
[xs.len()-1..1,-1].pump(Void,'wrap(i){ xs.swap(i,(0).random(0,i+1)) })
xs
}</
<pre>
var ns=(1).pump(10,List).copy() // [1..10] made mutable
|