Knuth shuffle
From Rosetta Code
(Redirected from Knuth Shuffle)
You are encouraged to solve this task according to the task description, using any language you may know.
Implement the Knuth shuffle (a.k.a. the Fisher-Yates shuffle) for an integer array (or, if possible, an array of any type). The Knuth shuffle is used to create a random permutation of an array.
[edit] ACL2
:set-state-ok t
(defun array-swap (name array i j)
(let ((ai (aref1 name array i))
(aj (aref1 name array j)))
(aset1 name
(aset1 name array j ai)
i aj)))
(defun shuffle-r (name array m state)
(if (zp m)
(mv array state)
(mv-let (i state)
(random$ m state)
(shuffle-r name
(array-swap name array i m)
(1- m)
state))))
(defun shuffle (name array state)
(shuffle-r name
array
(1- (first (dimensions name array)))
state))
[edit] Ada
This implementation is a generic shuffle routine, able to shuffle an array of any type.
generic
type Element_Type is private;
type Array_Type is array (Positive range <>) of Element_Type;
procedure Generic_Shuffle (List : in out Array_Type);
with Ada.Numerics.Discrete_Random;
procedure Generic_Shuffle (List : in out Array_Type) is
package Discrete_Random is new Ada.Numerics.Discrete_Random(Result_Subtype => Integer);
use Discrete_Random;
K : Integer;
G : Generator;
T : Element_Type;
begin
Reset (G);
for I in reverse List'Range loop
K := (Random(G) mod I) + 1;
T := List(I);
List(I) := List(K);
List(K) := T;
end loop;
end Generic_Shuffle;
An example using Generic_Shuffle.
with Ada.Text_IO;
with Generic_Shuffle;
procedure Test_Shuffle is
type Integer_Array is array (Positive range <>) of Integer;
Integer_List : Integer_Array
:= (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18);
procedure Integer_Shuffle is new Generic_Shuffle(Element_Type => Integer,
Array_Type => Integer_Array);
begin
for I in Integer_List'Range loop
Ada.Text_IO.Put(Integer'Image(Integer_List(I)));
end loop;
Integer_Shuffle(List => Integer_List);
Ada.Text_IO.New_Line;
for I in Integer_List'Range loop
Ada.Text_IO.Put(Integer'Image(Integer_List(I)));
end loop;
end Test_Shuffle;
[edit] ALGOL 68
PROC between = (INT a, b)INT :
(
ENTIER (random * ABS (b-a+1) + (a<b|a|b))
);
PROC knuth shuffle = (REF[]INT a)VOID:
(
FOR i FROM LWB a TO UPB a DO
INT j = between(LWB a, UPB a);
INT t = a[i];
a[i] := a[j];
a[j] := t
OD
);
main:(
[20]INT a;
FOR i FROM 1 TO 20 DO a[i] := i OD;
knuth shuffle(a);
print(a)
)
[edit] AppleScript
set n to 25
set array to {}
repeat with i from 1 to n
set end of array to i
end repeat
copy {array, array} to {unshuffled, shuffled}
repeat with i from n to 1 by -1
set j to (((random number) * (i - 1)) as integer) + 1
set shuffled's item i to array's item j
if j ≠ i's contents then set array's item j to array's item i
end repeat
return {unshuffled, shuffled}
Example:
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25},
{14, 25, 3, 1, 12, 18, 11, 20, 16, 15, 21, 5, 22, 19, 2, 24, 8, 10, 13, 6, 17, 23, 9, 7, 4}}
[edit] AutoHotkey
ahk forum: discussion
MsgBox % shuffle("1,2,3,4,5,6,7,8,9")
MsgBox % shuffle("1,2,3,4,5,6,7,8,9")
shuffle(list) { ; shuffle comma separated list, converted to array
StringSplit a, list, `, ; make array (length = a0)
Loop % a0-1 {
Random i, A_Index, a0 ; swap item 1,2... with a random item to the right of it
t := a%i%, a%i% := a%A_Index%, a%A_Index% := t
}
Loop % a0 ; construct string from sorted array
s .= "," . a%A_Index%
Return SubStr(s,2) ; drop leading comma
}
[edit] AutoIt
Dim $a[10]
ConsoleWrite('array before permutation:' & @CRLF)
For $i = 0 To 9
$a[$i] = Random(20,100,1)
ConsoleWrite($a[$i] & ' ')
Next
ConsoleWrite(@CRLF)
_Permute($a)
ConsoleWrite('array after permutation:' & @CRLF)
For $i = 0 To UBound($a) -1
ConsoleWrite($a[$i] & ' ')
Next
ConsoleWrite(@CRLF)
Func _Permute(ByRef $array)
Local $random, $tmp
For $i = UBound($array) -1 To 0 Step -1
$random = Random(0,$i,1)
$tmp = $array[$random]
$array[$random] = $array[$i]
$array[$i] = $tmp
Next
EndFunc
Output:
array before permutation: 43 57 37 20 97 98 69 76 97 70 array after permutation: 57 69 97 70 37 97 20 76 43 98
[edit] AWK
Many arrays in AWK have the first index at 1. This example shows how to shuffle such arrays. The elements can be integers, floating-point numbers, or strings.
# Shuffle an _array_ with indexes from 1 to _len_.
function shuffle(array, len, i, j, t) {
for (i = len; i > 1; i--) {
# j = random integer from 1 to i
j = int(i * rand()) + 1
# swap array[i], array[j]
t = array[i]
array[i] = array[j]
array[j] = t
}
}
# Test program.
BEGIN {
len = split("11 22 33 44 55 66 77 88 99 110", array)
shuffle(array, len)
for (i = 1; i < len; i++) printf "%s ", array[i]
printf "%s\n", array[len]
}
[edit] BASIC
RANDOMIZE TIMER
DIM cards(51) AS INTEGER
DIM L0 AS LONG, card AS LONG
PRINT "before:"
FOR L0 = 0 TO 51
cards(L0) = L0
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT
FOR L0 = 51 TO 0 STEP -1
card = INT(RND * (L0 + 1))
IF card <> L0 THEN SWAP cards(card), cards(L0)
NEXT
PRINT : PRINT "after:"
FOR L0 = 0 TO 51
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT
Sample output:
before: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 after: 27 14 37 35 3 44 25 38 46 1 22 49 2 51 16 32 20 30 4 33 36 6 31 21 41 34 9 13 0 50 47 48 40 39 7 18 19 26 24 10 29 5 12 28 11 17 43 45 8 23 42 15
[edit] BBC BASIC
cards% = 52
DIM pack%(cards%)
FOR I% = 1 TO cards%
pack%(I%) = I%
NEXT I%
FOR N% = cards% TO 2 STEP -1
SWAP pack%(N%),pack%(RND(N%))
NEXT N%
FOR I% = 1 TO cards%
PRINT pack%(I%);
NEXT I%
[edit] bc
I provide a shuffle() function. It can only shuffle an array of numbers. It fails if the array has more than 32768 elements. It always shuffles the array named shuffle[]; the array is not a function parameter because bc passes arrays by copying.
This code requires a bc with long names; the test program also requires a bc with the print statement.
seed = 1 /* seed of the random number generator */Output:
scale = 0
/* Random number from 0 to 32767. */
define rand() {
/* Formula (from POSIX) for random numbers of low quality. */
seed = (seed * 1103515245 + 12345) % 4294967296
return ((seed / 65536) % 32768)
}
/* Shuffle the first _count_ elements of shuffle[]. */
define shuffle(count) {
auto b, i, j, t
i = count
while (i > 0) {
/* j = random number in [0, i) */
b = 32768 % i /* want rand() >= b */
while (1) {
j = rand()
if (j >= b) break
}
j = j % i
/* decrement i, swap shuffle[i] and shuffle[j] */
t = shuffle[--i]
shuffle[i] = shuffle[j]
shuffle[j] = t
}
}
/* Test program. */
define print_array(count) {
auto i
for (i = 0; i < count - 1; i++) print shuffle[i], ", "
print shuffle[i], "\n"
}
for (i = 0; i < 10; i++) shuffle[i] = 11 * (i + 1)
"Original array: "; trash = print_array(10)
trash = shuffle(10)
"Shuffled array: "; trash = print_array(10)
quit
Original array: 11, 22, 33, 44, 55, 66, 77, 88, 99, 110 Shuffled array: 66, 44, 11, 55, 33, 77, 110, 22, 88, 99
[edit] Brat
shuffle = { a |
(a.length - 1).to 1 { i |
random_index = random(0, i)
temp = a[i]
a[i] = a[random_index]
a[random_index] = temp
}
a
}
p shuffle [1 2 3 4 5 6 7]
[edit] C
This shuffles any "object"; it imitates qsort in the syntax.
#include <stdlib.h>
#include <string.h>
int rrand(int m)
{
return (int)((double)m * ( rand() / (RAND_MAX+1.0) ));
}
#define BYTE(X) ((unsigned char *)(X))
void shuffle(void *obj, size_t nmemb, size_t size)
{
void *temp = malloc(size);
size_t n = nmemb;
while ( n > 1 ) {
size_t k = rrand(n--);
memcpy(temp, BYTE(obj) + n*size, size);
memcpy(BYTE(obj) + n*size, BYTE(obj) + k*size, size);
memcpy(BYTE(obj) + k*size, temp, size);
}
free(temp);
}
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 <stdio.h>
#include <stdlib.h>
/* define a shuffle function. e.g. decl_shuffle(double).
* advantage: compiler is free to optimize the swap operation without
* indirection with pointers, which could be much faster.
* disadvantage: each datatype needs a separate instance of the function.
* for a small funciton like this, it's not very big a deal.
*/
#define decl_shuffle(type) \
void shuffle_##type(type *list, size_t len) { \
int j; \
type tmp; \
while(len) { \
j = irand(len); \
if (j != len - 1) { \
tmp = list[j]; \
list[j] = list[len - 1]; \
list[len - 1] = tmp; \
} \
len--; \
} \
} \
/* random integer from 0 to n-1 */
int irand(int n)
{
int r, rand_max = RAND_MAX - (RAND_MAX % n);
/* reroll until r falls in a range that can be evenly
* distributed in n bins. Unless n is comparable to
* to RAND_MAX, it's not *that* important really. */
while ((r = rand()) >= rand_max);
return r / (rand_max / n);
}
/* declare and define int type shuffle function from macro */
decl_shuffle(int);
int main()
{
int i, x[20];
for (i = 0; i < 20; i++) x[i] = i;
for (printf("before:"), i = 0; i < 20 || !printf("\n"); i++)
printf(" %d", x[i]);
shuffle_int(x, 20);
for (printf("after: "), i = 0; i < 20 || !printf("\n"); i++)
printf(" %d", x[i]);
return 0;
}
[edit] C++
Compiler: g++ (version 4.3.2 20081105 (Red Hat 4.3.2-7))
#include <cstdlib>
#include <algorithm>
#include <iterator>
template<typename RandomAccessIterator>
void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
for(unsigned int n = end - begin - 1; n >= 1; --n) {
unsigned int k = rand() % (n + 1);
if(k != n) {
std::iter_swap(begin + k, begin + n);
}
}
}
The standard library provides this in the form of std::random_shuffle.
#include <algorithm>
#include <vector>
int main()
{
int array[] = { 1,2,3,4,5,6,7,8,9 }; // C-style array of integers
std::vector<int> vec(array, array + 9); // build STL container from int array
std::random_shuffle(array, array + 9); // shuffle C-style array
std::random_shuffle(vec.begin(), vec.end()); // shuffle STL container
}
[edit] C#
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(array.Length);
T temp = array[i]; array[i] = array[j]; array[j] = temp;
}
}
[edit] Clojure
(defn shuffle [vect]
(reduce (fn [v i] (let [r (rand-int i)]
(assoc v i (v r) r (v i)))
vect (range (dec (count vect)) 1 -1)))
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.
[edit] CMake
# shuffle(<output variable> [<value>...]) shuffles the values, and
# stores the result in a list.
function(shuffle var)
set(forever 1)
# Receive ARGV1, ARGV2, ..., ARGV${last} as an array of values.
math(EXPR last "${ARGC} - 1")
# Shuffle the array with Knuth shuffle (Fisher-Yates shuffle).
foreach(i RANGE ${last} 1)
# Roll j = a random number from 1 to i.
math(EXPR min "100000000 % ${i}")
while(forever)
string(RANDOM LENGTH 8 ALPHABET 0123456789 j)
if(NOT j LESS min) # Prevent modulo bias when j < min.
break() # Break loop when j >= min.
endif()
endwhile()
math(EXPR j "${j} % ${i} + 1")
# Swap ARGV${i} with ARGV${j}.
set(t ${ARGV${i}})
set(ARGV${i} ${ARGV${j}})
set(ARGV${j} ${t})
endforeach(i)
# Convert array to list.
set(answer)
foreach(i RANGE 1 ${last})
list(APPEND answer ${ARGV${i}})
endforeach(i)
set("${var}" ${answer} PARENT_SCOPE)
endfunction(shuffle)
shuffle(result 11 22 33 44 55 66)
message(STATUS "${result}")
# One possible output:
# -- 66;33;22;55;44;11
[edit] CoffeeScript
knuth_shuffle = (a) ->
n = a.length
while n > 1
r = Math.floor(n * Math.random())
n -= 1
[a[n], a[r]] = [a[r], a[n]]
a
counts =
"1,2,3": 0
"1,3,2": 0
"2,1,3": 0
"2,3,1": 0
"3,1,2": 0
"3,2,1": 0
for i in [1..100000]
counts[knuth_shuffle([ 1, 2, 3 ]).join(",")] += 1
for key, val of counts
console.log "#{key}: #{val}"
output
> coffee knuth_shuffle.coffee 1,2,3: 16714 1,3,2: 16566 2,1,3: 16460 2,3,1: 16715 3,1,2: 16750 3,2,1: 16795
[edit] Common Lisp
(defun nshuffle (sequence)
(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 aref rather than elt):
(defun nshuffle (sequence)
(etypecase sequence
(list (nshuffle-list sequence))
(array (nshuffle-array sequence))))
(defun nshuffle-list (list)
"Shuffle the list using an intermediate vector."
(let ((array (nshuffle-array (coerce list 'vector))))
(declare (dynamic-extent array))
(map-into list 'identity array)))
(defun nshuffle-array (array)
(loop for i from (length array) downto 2
do (rotatef (aref array (random i))
(aref array (1- i)))
finally (return array)))
[edit] D
[edit] Standard Version
A variant of the Knuth shuffle is in the D standard library Phobos:
import std.stdio, std.random;
void main() {
auto a = [1, 2, 3, 4, 5, 6, 7, 8, 9];
a.randomShuffle();
writeln(a);
}
- Output:
[8, 9, 3, 1, 7, 5, 4, 6, 2]
[edit] One Implementation
This shuffles any collection that supports random access and defines length, the items must be copyable (such template constraints may be added to shuffle):
import std.stdio, std.algorithm, std.random;
void shuffle(Range)(Range r) {
foreach_reverse (i; 1 .. r.length)
swap(r[i], r[uniform(0, i + 1)]);
}
void main() {
auto a = [1, 2, 3, 4, 5, 6, 7, 8, 9];
a.shuffle();
writeln(a);
}
[edit] Delphi
[edit] DWScript
procedure KnuthShuffle(a : array of Integer);
var
i, j, tmp : Integer;
begin
for i:=a.High downto 1 do begin
j:=RandomInt(a.Length);
tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;
end;
end;
[edit] E
def shuffle(array, random) {
for bound in (2..(array.size())).descending() {
def i := random.nextInt(bound)
def swapTo := bound - 1
def t := array[swapTo]
array[swapTo] := array[i]
array[i] := t
}
}
? def arr := [1,2,3,4,5,6,7,8,9,10].diverge()
# value: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].diverge()
? shuffle(arr, entropy)
? arr
# value: [4, 5, 2, 9, 7, 8, 1, 3, 6, 10].diverge()
[edit] Euphoria
sequence cards
cards = repeat(0,52)
integer card,temp
puts(1,"Before:\n")
for i = 1 to 52 do
cards[i] = i
printf(1,"%d ",cards[i])
end for
for i = 52 to 1 by -1 do
card = rand(i)
if card != i then
temp = cards[card]
cards[card] = cards[i]
cards[i] = temp
end if
end for
puts(1,"\nAfter:\n")
for i = 1 to 52 do
printf(1,"%d ",cards[i])
end for
[edit] Factor
There is a randomize word already in the standard library. Implementation:
: randomize ( seq -- seq )
dup length [ dup 1 > ]
[ [ iota random ] [ 1 - ] bi [ pick exchange ] keep ]
while drop ;
[edit] Fantom
class Main
{
static Void knuthShuffle (List array)
{
((array.size-1)..1).each |Int i|
{
r := Int.random(0..i)
array.swap (i, r)
}
}
public static Void main ()
{
List a := [1,2,3,4,5]
knuthShuffle (a)
echo (a)
List b := ["apples", "oranges", "pears", "bananas"]
knuthShuffle (b)
echo (b)
}
}
[edit] Forth
include random.fs
: shuffle ( deck size -- )
2 swap do
dup i random cells +
over @ over @ swap
rot ! over !
cell+
-1 +loop drop ;
: .array 0 do dup @ . cell+ loop drop ;
create deck 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,
deck 10 2dup shuffle .array
[edit] Fortran
program Knuth_Shuffle
implicit none
integer, parameter :: reps = 1000000
integer :: i, n
integer, dimension(10) :: a, bins = 0, initial = (/ (n, n=1,10) /)
do i = 1, reps
a = initial
call Shuffle(a)
where (a == initial) bins = bins + 1 ! skew tester
end do
write(*, "(10(i8))") bins
! prints 100382 100007 99783 100231 100507 99921 99941 100270 100290 100442
contains
subroutine Shuffle(a)
integer, intent(inout) :: a(:)
integer :: i, randpos, temp
real :: r
do i = size(a), 2, -1
call random_number(r)
randpos = int(r * i) + 1
temp = a(randpos)
a(randpos) = a(i)
a(i) = temp
end do
end subroutine Shuffle
end program Knuth_Shuffle
[edit] 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:
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
Here's the modified Knuth shuffle which shuffles the original array in place
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
Example:
> KnuthShuffle [| "Darrell"; "Marvin"; "Doug"; "Greg"; "Sam"; "Ken" |];;
val it : string array = [|"Marvin"; "Doug"; "Sam"; "Darrell"; "Ken"; "Greg"|]
[edit] GAP
# Return the list L after applying Knuth shuffle.
Shuffle := function(L)
local i, j, n;
n := Length(L);
for i in [n, n-1 .. 1] do
j := Random(1, i);
x := L[i];
L[i] := L[j];
L[j] := x;
od;
return L;
end;
# Return a ''Permutation'' object (a permutation of 1..n).
# They are printed in gap, in cycle decomposition form.
PermShuffle := n -> PermListList([1 .. n], Shuffle([1 .. n]));
Shuffle([1..10]);
# [ 4, 7, 1, 5, 8, 2, 6, 9, 10, 3 ]
PermShuffle(10);
# (1,9)(2,3,6,4,5,10,8,7)
# One may also call the built-in random generator on the symmetric group :
Random(SymmetricGroup(10));
(1,8,2,5,9,6)(3,4,10,7)
[edit] Go
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
var a [20]int
for i := range a {
a[i] = i
}
fmt.Println(a)
rand.Seed(time.Now().UnixNano())
for i := len(a) - 1; i >= 1; i-- {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
fmt.Println(a)
}
To shuffle any type:
package main
import (
"fmt"
"math/rand"
"time"
)
// Generic Knuth Shuffle algorithm. In Go, this is done with interface
// types. The parameter s of function shuffle is an interface type.
// Any type satisfying the interface "shuffler" can be shuffled with
// this function. Since the shuffle function uses the random number
// generator, it's nice to seed the generator at program load time.
func init() {
rand.Seed(time.Now().UnixNano())
}
func shuffle(s shuffler) {
for i := s.Len() - 1; i >= 1; i-- {
j := rand.Intn(i + 1)
s.Swap(i, j)
}
}
// Conceptually, a shuffler is an indexed collection of things.
// It requires just two simple methods.
type shuffler interface {
Len() int // number of things in the collection
Swap(i, j int) // swap the two things indexed by i and j
}
// ints is an example of a concrete type implementing the shuffler
// interface.
type ints []int
func (s ints) Len() int { return len(s) }
func (s ints) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
// Example program. Make an ints collection, fill with sequential numbers,
// print, shuffle, print.
func main() {
a := make(ints, 20)
for i := range a {
a[i] = i
}
fmt.Println(a)
shuffle(a)
fmt.Println(a)
}
Example output (of either program)
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19] [11 10 12 19 4 13 15 17 14 2 5 18 8 0 6 9 7 3 1 16]
[edit] Groovy
Solution:
def shuffle = { list ->
if (list == null || list.empty) return list
def r = new Random()
def n = list.size()
(n..1).each { i ->
def j = r.nextInt(i)
list[[i-1, j]] = list[[j, i-1]]
}
list
}
Test:
def list = [] + (0..20)
println list
println shuffle(list)
println shuffle(list)
println shuffle(list)
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [12, 16, 7, 13, 1, 9, 17, 20, 15, 3, 5, 6, 8, 0, 18, 10, 14, 4, 2, 11, 19] [17, 6, 10, 1, 18, 5, 7, 13, 2, 11, 16, 3, 14, 0, 4, 20, 19, 12, 8, 9, 15] [6, 20, 11, 4, 7, 12, 5, 14, 19, 18, 13, 15, 1, 2, 8, 16, 17, 10, 0, 9, 3]
[edit] Haskell
import System.Random
import Data.List
import Control.Monad
import Control.Arrow
mkRands = mapM (randomRIO.(,)0 ). enumFromTo 1. pred
replaceAt :: Int -> a -> [a] -> [a]
replaceAt i c = let (a,b) = splitAt i l in a++x:(drop 1 b)
swapElems :: (Int, Int) -> [a] -> [a]
swapElems (i,j) xs | i==j = xs
| otherwise = replaceAt j (xs!!i) $ replaceAt i (xs!!j) xs
knuthShuffle :: [a] -> IO [a]
knuthShuffle xs =
liftM (foldr swapElems xs. zip [1..]) (mkRands (length xs))
Examples of use:
*Main> knuthShuffle ['a'..'k'] "bhjdgfciake" *Main> knuthShuffle $ map(ap (,)(+10)) [0..9] [(0,10),(8,18),(2,12),(3,13),(9,19),(4,14),(7,17),(1,11),(6,16),(5,15)]
Function for showing intermediate results:
knuthShuffleProcess :: (Show a) => [a] -> IO ()
knuthShuffleProcess =
(mapM_ print. reverse =<<). ap (fmap. (. zip [1..]). scanr swapElems) (mkRands. length)
Detailed output example:
*Main> knuthShuffleProcess ['a'..'k'] "abcdefghijk" "abckefghijd" "jbckefghiad" "jbckeighfad" "jbckeihgfad" "jbhkeicgfad" "jbhiekcgfad" "jbeihkcgfad" "ibejhkcgfad" "iebjhkcgfad" "iebjhkcgfad"
An imperative implementation using arrays and the ST monad:
import Data.Array.ST
import Data.STRef
import Control.Monad
import Control.Monad.ST
import Control.Arrow
import System.Random
shuffle :: RandomGen g => [a] -> g -> ([a], g)
shuffle list g = runST $ do
r <- newSTRef g
let rand range = liftM (randomR range) (readSTRef r) >>=
runKleisli (second (Kleisli $ writeSTRef r) >>> arr fst)
a <- newAry (1, len) list
forM_ [len, len - 1 .. 2] $ \n -> do
k <- rand (1, n)
liftM2 (,) (readArray a k) (readArray a n) >>=
runKleisli (Kleisli (writeArray a n) *** Kleisli (writeArray a k))
liftM2 (,) (getElems a) (readSTRef r)
where len = length list
newAry :: (Int, Int) -> [a] -> ST s (STArray s Int a)
newAry = newListArray
[edit] Icon and Unicon
The shuffle method used here can shuffle lists, record fields, and strings:
procedure main()
show(shuffle([3,1,4,1,5,9,2,6,3]))
show(shuffle("this is a string"))
end
procedure shuffle(A)
every A[i := *A to 1 by -1] :=: A[?i]
return A
end
procedure show(A)
every writes(!A," ")
write()
end
Output:
->ks 9 6 1 4 3 1 3 5 2 i n t i s r t g h s a i s ->
Note that the gloriously succinct 'standard' Icon shuffle:
procedure shuffle(A)
every !A :=: ?A
end
is subtly biased.
[edit] Inform 6
[ shuffle a n i j tmp;
for(i = n - 1: i > 0: i--)
{
j = random(i + 1) - 1;
tmp = a->j;
a->j = a->i;
a->i = tmp;
}
];
[edit] J
KS=:{~ (2&{.@[ {`(|.@[)`]} ])/@(,~(,.?@>:))@i.@#
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.
process J
fold swap transform array <==> f / g y
Example of a transformed input:
(,~(,.?@>:))@i.@# 1+i.6
0 0 0 0 0 0
1 1 0 0 0 0
2 0 0 0 0 0
3 2 0 0 0 0
4 3 0 0 0 0
5 0 0 0 0 0
0 1 2 3 4 5
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:
2&{.@[ {`(|.@[)`]} ]
Finally, the shuffled indexes select elements from the original array.
input { ~ shuffled indexes
Alternatively, instead of creating a rectangular array, the swapping indices and the original data can be individually boxed.
In other words, (,~ (,. ?@>:))@i.@# can be replaced with |.@; ;&~./@(,. ?@>:)@i.@#, and the swapping can be achieved using (<@C. >)/ instead of (2&{.@[ {`(|.@[)`]} ])/.
With this approach, the data structure with the swapping indices and the original data could look like this:
(|.@; ;&~./@(,. ?@>:)@i.@#)'abcde'
+---+-+---+---+-+-----+
|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 (C.)).
The resulting definition looks like this:
KS=: [: > (<@C. >)/@(|.@; ;&~./@(,. ?@>:)@i.@#)
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:]A=: 5+i.9Shuffle:
5 6 7 8 9 10 11 12 13
KS AInput
13 10 7 5 11 9 8 6 12
]M=: /:~(1 2 3,:2 3 4),(11 2 3,: 0 11 2),(1 1 1,:1 0),:1 1 1,:1 0 1Shuffle
1 1 1
1 0 0
1 1 1
1 0 1
1 2 3
2 3 4
11 2 3
0 11 2
KS MInput
11 2 3
0 11 2
1 1 1
1 0 1
1 1 1
1 0 0
1 2 3
2 3 4
]L=:'aA';'bbB';'cC%$';'dD@'Shuffle
+--+---+----+---+
|aA|bbB|cC%$|dD@|
+--+---+----+---+
KS L
+--+----+---+---+
|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 ):
({~?~@#)
Applied on the former examples:
({~?~@#) A
8 7 13 6 10 11 5 9 12
({~?~@#) M
1 1 1
1 0 1
1 2 3
2 3 4
11 2 3
0 11 2
1 1 1
1 0 0
({~?~@#) L
+----+---+--+---+
|cC%$|bbB|aA|dD@|
+----+---+--+---+
[edit] Java
import java.util.Random;
public static final Random gen = new Random();
// version for array of ints
public static void shuffle (int[] array) {
int n = array.length;
while (n > 1) {
int k = gen.nextInt(n--); //decrements after using the value
int temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}
// version for array of references
public static void shuffle (Object[] array) {
int n = array.length;
while (n > 1) {
int k = gen.nextInt(n--); //decrements after using the value
Object temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}
[edit] JavaScript
function knuth_shuffle(a) {
var n = a.length,
r,
temp;
while (n > 1) {
r = Math.floor(n * Math.random());
n -= 1;
temp = a[n];
a[n] = a[r];
a[r] = temp;
}
return a;
}
var res, i, key;
res = {
'1,2,3': 0, '1,3,2': 0,
'2,1,3': 0, '2,3,1': 0,
'3,1,2': 0, '3,2,1': 0
};
for (i = 0; i < 100000; i++) {
res[knuth_shuffle([1,2,3]).join(',')] += 1;
}
for (key in res) {
print(key + "\t" + res[key]);
}
Results in:
1,2,3 16619 1,3,2 16614 2,1,3 16752 2,3,1 16959 3,1,2 16460 3,2,1 16596
[edit] 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):
(* Sorted array of 21 integers *)
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
knuth-shuffle.
Command line:
- joy shuffle.joy
Output:
usrlib is loaded inilib is loaded agglib is loaded [12 6 8 4 14 18 7 15 1 0 11 13 5 10 16 2 19 17 9 20 3]
[edit] LabVIEW
[edit] Liberty BASIC
'Declared the UpperBound to prevent confusion with lots of 9's floating around....
UpperBound = 9
Dim array(UpperBound)
For i = 0 To UpperBound
array(i) = Int(Rnd(1) * 10)
Print array(i)
Next i
For i = 0 To UpperBound
'set a random value because we will need to use the same value twice
randval = Int(Rnd(1) * (UpperBound - i))
temp1 = array(randval)
temp2 = array((UpperBound - i))
array(randval) = temp2
array((UpperBound - i)) = temp1
Next i
For i = 0 To UpperBound
Print array(i)
Next i
[edit] Logo
to swap :i :j :a
localmake "t item :i :a
setitem :i :a item :j :a
setitem :j :a :t
end
to shuffle :a
for [i [count :a] 2] [swap 1 + random :i :i :a]
end
make "a {1 2 3 4 5 6 7 8 9 10}
shuffle :a
show :a
Lhogho does not have a setitem, and also does things more 'function'ally.
to slice :lst :start :finish
local "res
make "res []
for "i [:start :finish 1] [
make "j item :i :lst
make "res se :res :j
]
op :res
end
to setitem :n :lst :val
local "lhs
local "rhs
make "lhs slice :lst 1 :n-1
make "rhs slice :lst :n+1 count :lst
op (se :lhs :val :rhs)
end
to swap :i :j :a
local "t
make "t item :i :a
make "a setitem :i :a item :j :a
make "a setitem :j :a :t
op :a
end
to shuffle :a
for "i [count :a 2]
[
make "a swap 1 + random :i :i :a
]
op :a
end
make "a ( list 1 2 3 4 5 6 7 8 9 10 )
make "a shuffle :a
show :a
[edit] Lua
function table.shuffle(t)
local n = #t
while n > 1 do
local k = math.random(n)
t[n], t[k] = t[k], t[n]
n = n - 1
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
[edit] M4
divert(-1)
define(`randSeed',141592653)
define(`rand_t',`eval(randSeed^(randSeed>>13))')
define(`random',
`define(`randSeed',eval((rand_t^(rand_t<<18))&0x7fffffff))randSeed')
define(`for',
`ifelse($#,0,``$0'',
`ifelse(eval($2<=$3),1,
`pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`set',`define(`$1[$2]',`$3')')
define(`get',`defn($1[$2])')
define(`new',`set($1,size,0)')
define(`deck',
`new($1)for(`x',1,$2,
`set(`$1',x,x)')`'set(`$1',size,$2)')
define(`show',
`for(`x',1,get($1,size),`get($1,x)`'ifelse(x,get($1,size),`',`, ')')')
define(`swap',`set($1,$2,get($1,$4))`'set($1,$4,$3)')
define(`shuffle',
`define(`s',get($1,size))`'for(`x',1,decr(s),
`swap($1,x,get($1,x),eval(x+random%(s-x+1)))')')
divert
deck(`b',52)
show(`b')
shuffle(`b')
show(`b')
Output:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 6, 22, 33, 51, 35, 45, 16, 32, 7, 34, 10, 44, 5, 38, 43, 25, 29, 9, 37, 20, 21, 48, 24, 46, 8, 26, 41, 47, 49, 36, 14, 31, 15, 39, 12, 17, 13, 1, 3, 4, 27, 11, 28, 2, 19, 30, 42, 50, 18, 52, 40, 23
[edit] Mathematica
Usage of built-in function:
RandomSample[{1, 2, 3, 4, 5, 6}]
Custom function:
Shuffle[input_List /; Length[input] >= 1] :=
Module[{indices = {}, allindices = Range[Length[input]]},
Do[
AppendTo[indices,
Complement[allindices, indices][[RandomInteger[{1, i}]]]];
,
{i, Length[input], 1, -1}
];
input[[indices]]
]
Example:
Shuffle[{1, 2, 3, 4, 5, 6}]
[edit] 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.
function list = knuthShuffle(list)
for i = (numel(list):-1:2)
j = floor(i*rand(1) + 1); %Generate random int between 1 and i
%Swap element i with element j.
list([j i]) = list([i j]);
end
end
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.
function list = randSort(list)
list = list( randperm(numel(list)) );
end
[edit] Maxima
/* Maxima has an implementation of Knuth shuffle */
random_permutation([a, b, c]);
[edit] Modula-3
MODULE Shuffle EXPORTS Main;
IMPORT IO, Fmt, Random;
VAR a := ARRAY [0..9] OF INTEGER {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
VAR temp: INTEGER;
n: INTEGER := NUMBER(a);
BEGIN
WITH rand = NEW(Random.Default).init() DO
WHILE n > 1 DO
WITH k = rand.integer(0, n - 1) DO
DEC(n);
temp := a[n];
a[n] := a[k];
a[k] := temp;
END;
END;
END;
END Shuffle;
BEGIN
Shuffle(a);
FOR i := FIRST(a) TO LAST(a) DO
IO.Put(Fmt.Int(a[i]) & " ");
END;
IO.Put("\n");
END Shuffle.
Output:
martin@thinkpad:~$ ./shuffle 9 2 7 3 6 8 4 5 1 10 martin@thinkpad:~$ ./shuffle 1 7 8 10 5 4 6 3 9 2
[edit] MUMPS
Shuffle(items,separator) New ii,item,list,n
Set list="",n=0
Set ii="" For Set ii=$Order(items(ii)) Quit:ii="" Do
. Set n=n+1,list(n)=items(ii),list=list_$Char(n)
. Quit
For Quit:list="" Do
. Set n=$Random($Length(list))+1
. Set item=list($ASCII(list,n))
. Set $Extract(list,n)=""
. Write item,separator
. Quit
Quit
CardDeck New card,ii,suite
Set ii=0
For suite="Spades","Hearts","Clubs","Diamonds" Do
. For card=2:1:10,"Jack","Queen","King","Ace" Do
. . Set ii=ii+1,items(ii)=card_" of "_suite
. . Quit
. Quit
Quit
Kill items
Set items(91)="Red"
Set items(82)="White"
Set items(73)="Blue"
Set items(64)="Yellow"
Set items(55)="Green"
Do Shuffle(.items," ") ; Red Yellow White Green Blue
Do Shuffle(.items," ") ; Red Blue Yellow White Green
Do Shuffle(.items," ") ; Green Blue Yellow White Red
Kill items Do CardDeck,Shuffle(.items,$Char(13,10))
Queen of Hearts
9 of Diamonds
10 of Hearts
King of Hearts
7 of Diamonds
9 of Clubs
6 of Diamonds
8 of Diamonds
Jack of Spades
Ace of Hearts
Queen of Diamonds
9 of Hearts
2 of Hearts
King of Clubs
10 of Spades
7 of Clubs
6 of Clubs
3 of Diamonds
3 of Spades
Queen of Clubs
Ace of Spades
4 of Hearts
Ace of Diamonds
7 of Spades
Ace of Clubs
King of Spades
10 of Diamonds
Jack of Diamonds
8 of Clubs
4 of Spades
Jack of Hearts
10 of Clubs
4 of Diamonds
3 of Hearts
2 of Diamonds
5 of Hearts
Jack of Clubs
2 of Clubs
5 of Diamonds
6 of Hearts
4 of Clubs
9 of Spades
3 of Clubs
5 of Spades
6 of Spades
7 of Hearts
8 of Spades
8 of Hearts
2 of Spades
Queen of Spades
King of Diamonds
5 of Clubs
[edit] Nemerle
Shuffle[T] (arr : array[T]) : array[T]
{
def rnd = Random();
foreach (i in [0 .. (arr.Length - 2)])
arr[i] <-> arr[(rnd.Next(i, arr.Length))];
arr
}
[edit] NetRexx
/* NetRexx */
options replace format comments java crossref savelog symbols nobinary
import java.util.List
cards = [String -
'hA', 'h2', 'h3', 'h4', 'h5', 'h6', 'h7', 'h8', 'h9', 'h10', 'hJ', 'hQ', 'hK' -
, 'cA', 'c2', 'c3', 'c4', 'c5', 'c6', 'c7', 'c8', 'c9', 'c10', 'cJ', 'cQ', 'cK' -
, 'dA', 'd2', 'd3', 'd4', 'd5', 'd6', 'd7', 'd8', 'd9', 'd10', 'dJ', 'dQ', 'dK' -
, 'sA', 's2', 's3', 's4', 's5', 's6', 's7', 's8', 's9', 's10', 'sJ', 'sQ', 'sK' -
]
cardsLen = cards.length
deck = ArrayList(cardsLen)
loop c_ = 0 to cardsLen - 1
deck.add(String(cards[c_]))
end c_
showHand(deck)
deck = ArrayList shuffle(deck)
showHand(deck)
return
method shuffle(deck = List) public static binary returns List
rn = Random()
dl = deck.size
loop i_ = dl - 1 to 1 by -1
j_ = rn.nextInt(i_)
__ = deck.get(i_)
deck.set(i_, deck.get(j_))
deck.set(j_, __)
end i_
return deck
method showHand(deck = ArrayList) public static binary
dl = deck.size
hl = dl % 4
loop c_ = 0 to dl - 1 by hl
d_ = c_ + hl
if d_ >= dl then d_ = dl
say ArrayList(deck.subList(c_, d_)).toString
end c_
say
return
- Output
[hA, h2, h3, h4, h5, h6, h7, h8, h9, h10, hJ, hQ, hK] [cA, c2, c3, c4, c5, c6, c7, c8, c9, c10, cJ, cQ, cK] [dA, d2, d3, d4, d5, d6, d7, d8, d9, d10, dJ, dQ, dK] [sA, s2, s3, s4, s5, s6, s7, s8, s9, s10, sJ, sQ, sK] [s8, c10, sJ, c8, h10, h3, s3, d6, hJ, d3, c7, h5, s5] [h8, d10, cK, s6, dQ, d9, d4, c4, c6, h6, cA, sA, dK] [dJ, dA, d7, c2, d2, s10, sK, h2, c5, s7, cJ, d5, h9] [c9, d8, c3, s9, cQ, sQ, h4, s4, hQ, h7, hK, hA, s2]
[edit] OCaml
let shuffle arr =
for n = Array.length arr - 1 downto 1 do
let k = Random.int (n + 1) in
let temp = arr.(n) in
arr.(n) <- arr.(k);
arr.(k) <- temp
done
[edit] Oz
declare
proc {Shuffle Arr}
Low = {Array.low Arr}
High = {Array.high Arr}
in
for I in High..Low;~1 do
J = Low + {OS.rand} mod (I - Low + 1)
OldI = Arr.I
in
Arr.I := Arr.J
Arr.J := OldI
end
end
X = {Tuple.toArray unit(0 1 2 3 4 5 6 7 8 9)}
in
{Show {Array.toRecord unit X}}
{Shuffle X}
{Show {Array.toRecord unit X}}
[edit] PARI/GP
FY(v)={
forstep(n=#v,2,-1,
my(i=random(n)+1,t=v[i]);
v[i]=v[n];
v[n]=t
);
v
};
FY(vector(52,i,i))
[edit] Pascal
program Knuth;
const
max = 10;
type
list = array [1..max] of integer;
procedure shuffle(var a: list);
var
i,k,tmp: integer;
begin
randomize;
for i := max downto 2 do begin
k := random(i) + 1;
if (a[i] <> a[k]) then begin
tmp := a[i]; a[i] := a[k]; a[k] := tmp
end
end
end;
{ Test and display }
var
a: list;
i: integer;
begin
for i := 1 to max do
a[i] := i;
shuffle(a);
for i := 1 to max do
write(a[i], ' ');
writeln
end.
Sample output:
2 7 10 4 3 5 1 9 6 8
[edit] Perl
sub shuffle {
my @a = @_;
foreach my $n (1 .. $#a) {
my $k = int rand $n + 1;
$k == $n or @a[$k, $n] = @a[$n, $k];
}
return @a;
}
[edit] Perl 6
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;
}
The shuffle is also built into the pick method on lists when you pass it a "whatever" for the number to pick:
my @deck = @cards.pick(*);
[edit] PHP
//The Fisher-Yates original Method
function yates_shuffle($arr){
$shuffled = Array();
while($arr){
$rnd = array_rand($arr);
$shuffled[] = $arr[$rnd];
array_splice($arr, $rnd, 1);
}
return $shuffled;
}
//The modern Durstenfeld-Knuth algorithm
function knuth_shuffle(&$arr){
for($i=count($arr)-1;$i>0;$i--){
$rnd = mt_rand(0,$i);
list($arr[$i], $arr[$rnd]) = array($arr[$rnd], $arr[$i]);
}
}
[edit] PicoLisp
(de shuffle (Lst)
(make
(for (N (length Lst) (gt0 N))
(setq Lst
(conc
(cut (rand 0 (dec 'N)) 'Lst)
(prog (link (car Lst)) (cdr Lst)) ) ) ) ) )
[edit] PL/I
declare T(0:10) fixed binary initial (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);
declare (i, j, temp) fixed binary;
do i = lbound(T,1) to hbound(T,1);
j = min(random() * 12, 11);
temp = T(j); T(j) = T(i); T(i) = temp;
end;
[edit] PowerShell
function shuffle ($a) {
$c = $a.Clone() # make copy to avoid clobbering $a
1..($c.Length - 1) | ForEach-Object {
$i = Get-Random -Minimum $_ -Maximum $c.Length
$c[$_-1],$c[$i] = $c[$i],$c[$_-1]
$c[$_-1] # return newly-shuffled value
}
$c[-1] # last value
}
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.
[edit] PureBasic
EnableExplicit
Procedure KnuthShuffle(Array a(1))
Protected i, last = ArraySize(a())
For i = last To 1 Step -1
Swap a(i), a(Random(i))
Next
EndProcedure
Procedure.s ArrayToString(Array a(1))
Protected ret$, i, last = ArraySize(a())
ret$ = Str(a(0))
For i = 1 To last
ret$ + "," + Str(a(i))
Next
ProcedureReturn ret$
EndProcedure
#NumElements = 10
Dim a(#NumElements-1)
Define i
For i = 0 To #NumElements-1
a(i) = i
Next
KnuthShuffle(a())
Debug "shuffled: " + ArrayToString(a())
Sample output:
shuffled: 1,8,6,0,5,9,2,4,7,3
[edit] Python
Python's standard library function random.shuffle uses this algorithm and so should normally be used. The function below is very similar:
from random import randrange
def knuth_shuffle(x):
for i in range(len(x)-1, 0, -1):
j = randrange(i + 1)
x[i], x[j] = x[j], x[i]
x = list(range(10))
knuth_shuffle(x)
print("shuffled:", x)
Sample output
shuffled: [5, 1, 6, 0, 8, 4, 2, 3, 9, 7]
[edit] R
See also, the built-in function 'sample'.
Original Fisher-Yates version
fisheryatesshuffle <- function(n)
{
pool <- seq_len(n)
a <- c()
while(length(pool) > 0)
{
k <- sample.int(length(pool), 1)
a <- c(a, pool[k])
pool <- pool[-k]
}
a
}
Knuth variation:
fisheryatesknuthshuffle <- function(n)
{
a <- seq_len(n)
while(n >=2)
{
k <- sample.int(n, 1)
if(k != n)
{
temp <- a[k]
a[k] <- a[n]
a[n] <- temp
}
n <- n - 1
}
a
}
#Example usage:
fisheryatesshuffle(6) # e.g. 1 3 6 2 4 5
x <- c("foo", "bar", "baz", "quux")
x[fisheryatesknuthshuffle(4)] # e.g. "bar" "baz" "quux" "foo"
[edit] Racket
#lang racket
(define (swap! vec i j)
(let ([tmp (vector-ref vec i)])
(vector-set! vec i (vector-ref vec j))
(vector-set! vec j tmp)))
(define (knuth-shuffle x)
(if (list? x)
(vector->list (knuth-shuffle (list->vector x)))
(begin (for ([i (in-range (sub1 (vector-length x)) 0 -1)])
(define r (random i))
(swap! x i r))
x)))
(knuth-shuffle '(1 2 3 4))
[edit] REBOL
rebol [
Title: "Fisher-Yates"
Purpose: {Fisher-Yates shuffling algorithm}
]
fisher-yates: func [b [block!] /local n i j k] [
n: length? b: copy b
i: n
while [i > 1] [
if i <> j: random i [
error? set/any 'k pick b j
change/only at b j pick b i
change/only at b i get/any 'k
]
i: i - 1
]
b
]
[edit] REXX
/*REXX program shuffles a deck of playing cards using the Knuth shuffle.*/
rank='ace duece trey 4 5 6 7 8 9 10 jack queen king'
suit='club spade diamond heart'
say '────────────────── getting a new deck out of the box...'
deck.1=' color joker' /*good decks have a color joker, */
deck.2=' b&w joker' /*∙∙∙ and a black & white joker. */
cards=2 /*now, two cards are in the deck.*/
do j =1 for words(suit)
do k=1 for words(rank)
cards=cards+1
deck.cards=right(word(suit,j),7) word(rank,k)
end /*k*/
end /*j*/
call showDeck 'ace' /*inserts blank when ACE is found*/
say '────────────────── shuffling' cards "cards..."
do s=cards by -1 to 1; rand=random(1,s)
if rand\==s then do /*swap two cards in the card deck*/
_=deck.rand
deck.rand=deck.s
deck.s=_
end
end /*s*/
call showDeck
say '────────────────── ready to play schafkopf (take out jokers first).'
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────SHOWDECK subroutine─────────────────*/
showDeck: parse arg break; say
do m=1 for cards
if pos(break,deck.m)\==0 then say /*blank, easier to read cards*/
say 'card' right(m,2) '───►' deck.m
end /*m*/
say
return
output
────────────────── getting a new deck out of the box... card 1 ───► color joker card 2 ───► b&w joker card 3 ───► club ace card 4 ───► club duece card 5 ───► club trey card 6 ───► club 4 card 7 ───► club 5 card 8 ───► club 6 card 9 ───► club 7 card 10 ───► club 8 card 11 ───► club 9 card 12 ───► club 10 card 13 ───► club jack card 14 ───► club queen card 15 ───► club king card 16 ───► spade ace card 17 ───► spade duece card 18 ───► spade trey card 19 ───► spade 4 card 20 ───► spade 5 card 21 ───► spade 6 card 22 ───► spade 7 card 23 ───► spade 8 card 24 ───► spade 9 card 25 ───► spade 10 card 26 ───► spade jack card 27 ───► spade queen card 28 ───► spade king card 29 ───► diamond ace card 30 ───► diamond duece card 31 ───► diamond trey card 32 ───► diamond 4 card 33 ───► diamond 5 card 34 ───► diamond 6 card 35 ───► diamond 7 card 36 ───► diamond 8 card 37 ───► diamond 9 card 38 ───► diamond 10 card 39 ───► diamond jack card 40 ───► diamond queen card 41 ───► diamond king card 42 ───► heart ace card 43 ───► heart duece card 44 ───► heart trey card 45 ───► heart 4 card 46 ───► heart 5 card 47 ───► heart 6 card 48 ───► heart 7 card 49 ───► heart 8 card 50 ───► heart 9 card 51 ───► heart 10 card 52 ───► heart jack card 53 ───► heart queen card 54 ───► heart king ────────────────── shuffling 54 cards... card 1 ───► diamond king card 2 ───► spade jack card 3 ───► spade 7 card 4 ───► club 4 card 5 ───► heart 7 card 6 ───► heart 10 card 7 ───► club jack card 8 ───► diamond duece card 9 ───► club 10 card 10 ───► diamond 5 card 11 ───► spade 10 card 12 ───► heart jack card 13 ───► club king card 14 ───► diamond 8 card 15 ───► heart 9 card 16 ───► spade ace card 17 ───► spade king card 18 ───► spade trey card 19 ───► color joker card 20 ───► heart 8 card 21 ───► diamond 7 card 22 ───► diamond jack card 23 ───► club duece card 24 ───► club 9 card 25 ───► club 5 card 26 ───► spade 9 card 27 ───► spade queen card 28 ───► heart 5 card 29 ───► spade 6 card 30 ───► club 8 card 31 ───► heart duece card 32 ───► diamond ace card 33 ───► spade 4 card 34 ───► diamond 9 card 35 ───► b&w joker card 36 ───► diamond 4 card 37 ───► heart king card 38 ───► club ace card 39 ───► spade duece card 40 ───► club trey card 41 ───► diamond queen card 42 ───► diamond 10 card 43 ───► spade 8 card 44 ───► diamond trey card 45 ───► club queen card 46 ───► heart ace card 47 ───► heart queen card 48 ───► heart trey card 49 ───► club 7 card 50 ───► club 6 card 51 ───► heart 4 card 52 ───► heart 6 card 53 ───► diamond 6 card 54 ───► spade 5 ────────────────── ready to play schafkopf (take out jokers first).
[edit] Ruby
class Array
def knuth_shuffle!
j = length
i = 0
while j > 1
r = i + rand(j)
self[i], self[r] = self[r], self[i]
i += 1
j -= 1
end
self
end
end
r = Hash.new(0)
100_000.times do |i|
a = [1,2,3].knuth_shuffle!
r[a] += 1
end
r.keys.sort.each {|a| puts "#{a.inspect} => #{r[a]}"}
results in
[1, 2, 3] => 16572 [1, 3, 2] => 16610 [2, 1, 3] => 16633 [2, 3, 1] => 16714 [3, 1, 2] => 16838 [3, 2, 1] => 16633
More idomatic:
class Array
def knuth_shuffle!
(length - 1).downto(1) do |i|
j = rand(i + 1)
self[i], self[j] = self[j], self[i]
end
self
end
end
[edit] Run BASIC
dim cards(52)
for i = 1 to 52 ' make deck
cards(i) = i
next
for i = 52 to 1 step -1 ' shuffle deck
r = int((rnd(1)*i) + 1)
if r <> i then
hold = cards(r)
cards(r) = cards(i)
cards(i) = hold
end if
next
print "== Shuffled Cards ==" ' print shuffled cards
for i = 1 to 52
print cards(i);" ";
if i mod 18 = 0 then print
next
[edit] Scala
def shuffle[T](a: Array[T]) = {
for (i <- 1 until a.size reverse) {
val j = util.Random nextInt (i + 1)
val t = a(i)
a(i) = a(j)
a(j) = t
}
a
}
[edit] Seed7
$ include "seed7_05.s7i";
const type: intArray is array integer;
const proc: shuffle (inout intArray: a) is func
local
var integer: i is 0;
var integer: k is 0;
var integer: tmp is 0;
begin
for i range maxIdx(a) downto 2 do
k := rand(1, i);
tmp := a[i];
a[i] := a[k];
a[k] := tmp;
end for;
end func;
const proc: main is func
local
var intArray: a is 10 times 0;
var integer: i is 0;
begin
for key i range a do
a[i] := i;
end for;
shuffle(a);
for i range a do
write(i <& " ");
end for;
writeln;
end func;
Output:
7 5 6 8 3 10 9 4 2 1
[edit] Smalltalk
"The selector swap:with: is documented, but it seems not
implemented (GNU Smalltalk version 3.0.4); so here it is an implementation"
SequenceableCollection extend [
swap: i with: j [
|t|
t := self at: i.
self at: i put: (self at: j).
self at: j put: t.
]
].
Object subclass: Shuffler [
Shuffler class >> Knuth: aSequenceableCollection [
|n k|
n := aSequenceableCollection size.
[ n > 1 ] whileTrue: [
k := Random between: 1 and: n.
aSequenceableCollection swap: n with: k.
n := n - 1
]
]
].
Testing
"Test"
|c|
c := OrderedCollection new.
c addAll: #( 1 2 3 4 5 6 7 8 9 ).
Shuffler Knuth: c.
c display.
[edit] SNOBOL4
* Library for random()
-include 'Random.sno'
* # String -> array
define('s2a(str,n)i') :(s2a_end)
s2a s2a = array(n); str = str ' '
sa1 str break(' ') . s2a<i = i + 1> span(' ') = :s(sa1)f(return)
s2a_end
* # Array -> string
define('a2s(a)i') :(a2s_end)
a2s a2s = a2s a<i = i + 1> ' ' :s(a2s)f(return)
a2s_end
* # Knuth shuffle in-place
define('shuffle(a)alen,n,k,tmp') :(shuffle_end)
shuffle n = alen = prototype(a);
sh1 k = convert(random() * alen,'integer') + 1
eq(a<n>,a<k>) :s(sh2)
tmp = a<n>; a<n> = a<k>; a<k> = tmp
sh2 n = gt(n,1) n - 1 :s(sh1)
shuffle = a :(return)
shuffle_end
* # Test and display
a = s2a('1 2 3 4 5 6 7 8 9 10',10)
output = a2s(a) '->'
shuffle(a)
output = a2s(a)
end
Sample Output:
1 2 3 4 5 6 7 8 9 10 -> 2 10 4 9 1 5 6 8 7 3
[edit] Tcl
proc knuth_shuffle lst {
set j [llength $lst]
for {set i 0} {$j > 1} {incr i;incr j -1} {
set r [expr {$i+int(rand()*$j)}]
set t [lindex $lst $i]
lset lst $i [lindex $lst $r]
lset lst $r $t
}
return $lst
}
% knuth_shuffle {1 2 3 4 5}
2 1 3 5 4
% knuth_shuffle {1 2 3 4 5}
5 2 1 4 3
% knuth_shuffle {tom dick harry peter paul mary}
tom paul mary harry peter dick
As a test of skewing (an indicator of a poor implementation) this code was used:
% for {set i 0} {$i<100000} {incr i} {
foreach val [knuth_shuffle {1 2 3 4 5}] pos {pos0 pos1 pos2 pos3 pos4} {
incr tots($pos) $val
}
}
% parray tots
tots(pos0) = 300006
tots(pos1) = 300223
tots(pos2) = 299701
tots(pos3) = 299830
tots(pos4) = 300240
[edit] TI-83 BASIC
Input L1, output L2.
:"SHUFFLE" :L1→L2 :dim(L2)→A :For(B,1,dim(L2)-1) :randInt(1,A)→C :L2(C)→D :L2(A)→L2(C) :D→L2(A) :A-1→A :End :DelVar A :DelVar B :DelVar C :DelVar D :Return
[edit] TUSCRIPT
$$ MODE TUSCRIPT
oldnumbers=newnumbers="",range=20
LOOP nr=1,#range
oldnumbers=APPEND(oldnumbers,nr)
ENDLOOP
PRINT "before ",oldnumbers
LOOP r=#range,1,-1
RANDNR=RANDOM_NUMBERS (1,#r,1)
shuffle=SELECT (oldnumbers,#randnr,oldnumbers)
newnumbers=APPEND(newnumbers,shuffle)
ENDLOOP
PRINT "after ",newnumbers
Output:
before 1'2'3'4'5'6'7'8'9'10'11'12'13'14'15'16'17'18'19'20 after 7'16'13'11'1'9'15'4'18'14'3'12'17'8'19'20'6'5'2'10
[edit] UNIX Shell
# Shuffle array[@].
function shuffle {
integer i j t
((i = ${#array[@]}))
while ((i > 1)); do
((j = RANDOM)) # 0 <= j < 32768
((j < 32768 % i)) && continue # no modulo bias
((j %= i)) # 0 <= j < i
((i -= 1))
((t = array[i]))
((array[i] = array[j]))
((array[j] = t))
done
}
# Test program.
set -A array 11 22 33 44 55 66 77 88 99 110
shuffle
echo "${array[@]}"
[edit] Ursala
This function works on lists of any type and length, including character strings.
shuffle = @iNX ~&l->r ^jrX/~&l ~&lK8PrC
test program:
#cast %s
example = shuffle 'abcdefghijkl'
output:
'keacfjlbdigh'
[edit] VBScript
- Implementation
function shuffle( a )
dim i
dim r
randomize timer
for i = lbound( a ) to ubound( a )
r = int( rnd * ( ubound( a ) + 1 ) )
if r <> i then
swap a(i), a(r)
end if
next
shuffle = a
end function
sub swap( byref a, byref b )
dim tmp
tmp = a
a = b
b = tmp
end sub
- Invocation
dim a
a = array( 1,2,3,4,5,6,7,8,9)
wscript.echo "before: ", join( a, ", " )
shuffle a
wscript.echo "after: ", join( a, ", " )
shuffle a
wscript.echo "after: ", join( a, ", " )
wscript.echo "--"
a = array( now(), "cow", 123, true, sin(1), 16.4 )
wscript.echo "before: ", join( a, ", " )
shuffle a
wscript.echo "after: ", join( a, ", " )
shuffle a
wscript.echo "after: ", join( a, ", " )
- Output
before: 1, 2, 3, 4, 5, 6, 7, 8, 9 after: 6, 4, 1, 2, 7, 3, 5, 8, 9 after: 8, 7, 3, 2, 6, 5, 9, 1, 4 -- before: 16/02/2010 5:46:58 PM, cow, 123, True, 0.841470984807897, 16.4 after: True, 16.4, 16/02/2010 5:46:58 PM, 123, cow, 0.841470984807897 after: 16.4, 16/02/2010 5:46:58 PM, 123, 0.841470984807897, True, cow
[edit] Vedit macro language
The shuffle routine in Playing Cards shuffles text lines in edit buffer. This example shuffles numeric registers #0 to #19.
The output will be inserted in current edit buffer.
// Test main
#90 = Time_Tick // seed for random number generator
#99 = 20 // number of items in the array
IT("Before:") IN
for (#100 = 0; #100 < #99; #100++) {
#@100 = #100
Num_Ins(#@100, LEFT+NOCR) IT(" ")
}
IN
Call("SHUFFLE_NUMBERS")
IT("After:") IN
for (#100 = 0; #100 < #99; #100++) {
Num_Ins(#@100, LEFT+NOCR) IT(" ")
}
IN
Return
//--------------------------------------------------------------
// Shuffle numeric registers #0 to #nn
// #99 = number of registers to shuffle (nn-1)
//
:SHUFFLE_NUMBERS:
for (#91 = #99-1; #91 > 0; #91--) {
Call("RANDOM")
#101 = Return_Value
#102 = #@101; #@101 = #@91; #@91 = #102
}
Return
//--------------------------------------------------------------
// Generate random numbers in range 0 <= Return_Value < #91
// #90 = Seed (0 to 0x7fffffff)
// #91 = Scaling (0 to 0x10000)
//
:RANDOM:
#92 = 0x7fffffff / 48271
#93 = 0x7fffffff % 48271
#90 = (48271 * (#90 % #92) - #93 * (#90 / #92)) & 0x7fffffff
Return ((#90 & 0xffff) * #91 / 0x10000)
Output:
Before: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 After: 9 13 8 18 10 1 17 15 0 16 14 19 3 2 7 11 6 4 5 12
Categories:
- Programming Tasks
- Classic CS problems and programs
- ACL2
- Ada
- ALGOL 68
- AppleScript
- AutoHotkey
- AutoIt
- AWK
- BASIC
- BBC BASIC
- Bc
- Brat
- C
- C++
- C sharp
- Clojure
- CMake
- CoffeeScript
- Common Lisp
- D
- Delphi
- DWScript
- E
- Euphoria
- Factor
- Fantom
- Forth
- Fortran
- F Sharp
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Inform 6
- J
- Java
- JavaScript
- Joy
- LabVIEW
- Liberty BASIC
- Logo
- Lua
- M4
- Mathematica
- MATLAB
- Maxima
- Modula-3
- MUMPS
- Nemerle
- NetRexx
- OCaml
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PowerShell
- PureBasic
- Python
- R
- Racket
- REBOL
- REXX
- Ruby
- Run BASIC
- Scala
- Seed7
- Smalltalk
- SNOBOL4
- Tcl
- TI-83 BASIC
- TUSCRIPT
- UNIX Shell
- Ursala
- VBScript
- Vedit macro language
