Knuth shuffle: Difference between revisions
Line 262: | Line 262: | ||
void shuffle(Range)(Range r) { |
void shuffle(Range)(Range r) { |
||
foreach_reverse (i; 1 .. r.length) |
|||
swap(r[i], r[uniform( |
swap(r[i], r[uniform(0, i + 1)]); |
||
} |
} |
||
Line 270: | Line 270: | ||
shuffle(a); |
shuffle(a); |
||
writeln(a); |
writeln(a); |
||
} |
|||
</lang> |
|||
Knuth shuffle using the standard library: |
Knuth shuffle variant using the standard library: |
||
<lang d>import std.stdio, std.random; |
<lang d>import std.stdio, std.random; |
||
Revision as of 22:24, 23 February 2011
You are encouraged to solve this task according to the task description, using any language you may know.
Implement the Knuth shuffle (aka 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.
Ada
This implementation is a generic shuffle routine, able to shuffle an array of any type. <lang Ada> generic
type Element_Type is private; type Array_Type is array (Positive range <>) of Element_Type;
procedure Generic_Shuffle (List : in out Array_Type); </lang> <lang Ada> with Ada.Numerics.Discrete_Random;
procedure Generic_Shuffle (List : in out Array_Type) is
package Discrete_Random is new Ada.Numerics.Discrete_Random(Result_Subtype => Integer); use Discrete_Random; K : Integer; G : Generator; T : Element_Type;
begin
Reset (G); for I in reverse List'Range loop K := (Random(G) mod I) + 1; T := List(I); List(I) := List(K); List(K) := T; end loop;
end Generic_Shuffle; </lang> An example using Generic_Shuffle. <lang Ada> with Ada.Text_IO; with Generic_Shuffle;
procedure Test_Shuffle is
type Integer_Array is array (Positive range <>) of Integer;
Integer_List : Integer_Array := (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18); procedure Integer_Shuffle is new Generic_Shuffle(Element_Type => Integer, Array_Type => Integer_Array);
begin
for I in Integer_List'Range loop Ada.Text_IO.Put(Integer'Image(Integer_List(I))); end loop; Integer_Shuffle(List => Integer_List); Ada.Text_IO.New_Line; for I in Integer_List'Range loop Ada.Text_IO.Put(Integer'Image(Integer_List(I))); end loop;
end Test_Shuffle; </lang>
ALGOL 68
<lang algol68>PROC between = (INT a, b)INT : (
ENTIER (random * ABS (b-a+1) + (a<b|a|b))
);
PROC knuth shuffle = (REF[]INT a)VOID: (
FOR i FROM LWB a TO UPB a DO INT j = between(LWB a, UPB a); INT t = a[i]; a[i] := a[j]; a[j] := t OD
);</lang>
<lang algol68>main:(
[20]INT a; FOR i FROM 1 TO 20 DO a[i] := i OD; knuth shuffle(a); print(a)
)</lang>
AppleScript
<lang AppleScript>set n to 25
set array to {} repeat with i from 1 to n set end of array to i end repeat copy {array, array} to {unshuffled, shuffled} repeat with i from n to 1 by -1 set j to (((random number) * (i - 1)) as integer) + 1 set shuffled's item i to array's item j if j ≠ i's contents then set array's item j to array's item i end repeat
return {unshuffled, shuffled}</lang>Example:<lang AppleScript>{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25}, {14, 25, 3, 1, 12, 18, 11, 20, 16, 15, 21, 5, 22, 19, 2, 24, 8, 10, 13, 6, 17, 23, 9, 7, 4}}</lang>
AutoHotkey
ahk forum: discussion <lang AutoHotkey>MsgBox % shuffle("1,2,3,4,5,6,7,8,9") MsgBox % shuffle("1,2,3,4,5,6,7,8,9")
shuffle(list) { ; shuffle comma separated list, converted to array
StringSplit a, list, `, ; make array (length = a0) Loop % a0-1 { Random i, A_Index, a0 ; swap item 1,2... with a random item to the right of it t := a%i%, a%i% := a%A_Index%, a%A_Index% := t } Loop % a0 ; construct string from sorted array s .= "," . a%A_Index% Return SubStr(s,2) ; drop leading comma
}</lang>
BASIC
<lang qbasic>RANDOMIZE TIMER
DIM cards(51) AS INTEGER DIM L0 AS LONG, card AS LONG
PRINT "before:" FOR L0 = 0 TO 51
cards(L0) = L0 PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT
FOR L0 = 51 TO 0 STEP -1
card = INT(RND * (L0 + 1)) IF card <> L0 THEN SWAP cards(card), cards(L0)
NEXT
PRINT : PRINT "after:" FOR L0 = 0 TO 51
PRINT LTRIM$(STR$(cards(L0))); " ";
NEXT PRINT</lang>
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
Brat
<lang brat>shuffle = { a |
(a.length - 1).to 1 { i | random_index = random(0, i) temp = a[i] a[i] = a[random_index] a[random_index] = temp }
a
}
p shuffle [1 2 3 4 5 6 7]</lang>
C
This shuffles any "object"; it imitates qsort in the syntax.
<lang c>#include <stdlib.h>
- include <string.h>
int rrand(int m) {
return (int)((double)m * ( rand() / (RAND_MAX+1.0) ));
}
- define BYTE(X) ((unsigned char *)(X))
void shuffle(void *obj, size_t nmemb, size_t size) {
void *temp = malloc(size); size_t n = nmemb; while ( n > 1 ) { size_t k = rrand(n--); memcpy(temp, BYTE(obj) + n*size, size); memcpy(BYTE(obj) + n*size, BYTE(obj) + k*size, size); memcpy(BYTE(obj) + k*size, temp, size); } free(temp);
} </lang>
C++
Compiler: g++ (version 4.3.2 20081105 (Red Hat 4.3.2-7))
<lang cpp>#include <cstdlib>
- include <algorithm>
- include <iterator>
template<typename RandomAccessIterator> void knuthShuffle(RandomAccessIterator begin, RandomAccessIterator end) {
for(unsigned int n = end - begin - 1; n >= 1; --n) { unsigned int k = rand() % (n + 1); if(k != n) { std::iter_swap(begin + k, begin + n); } }
}</lang>
The standard library provides this in the form of std::random_shuffle.
<lang cpp>#include <algorithm>
- include <vector>
int main() {
int array[] = { 1,2,3,4,5,6,7,8,9 }; // C-ctyle array of integers std::vector<int> vec(array, array + 9); // build STL container from int array
std::random_shuffle(array, array + 9); // shuffle C-style array std::random_shuffle(vec.begin(), vec.end()); // shuffle STL container
}</lang>
C#
<lang csharp>public static void KnuthShuffle<T>(T[] array) {
System.Random random = new System.Random(); for (int i = 0; i < array.Length; i++) { int j = random.Next(array.Length); T temp = array[i]; array[i] = array[j]; array[j] = temp; }
}</lang>
Clojure
<lang lisp>(defn shuffle [vect]
(reduce (fn [v i] (let [r (rand-int i)] (assoc v i (v r) r (v i))) vect (range (dec (count vect)) 1 -1)))</lang>
This works by generating a sequence of end-indices from n-1 to 1, then reducing that sequence (starting with the original vector) through a function that, given a vector and end-index, performs a swap between the end-index and some random index less than the end-index.
Common Lisp
<lang lisp>(defun nshuffle (sequence)
(loop for i from (length sequence) downto 2 do (rotatef (elt sequence (random i)) (elt sequence (1- i)))) sequence)</lang>
This operates on arbitrary sequences, but will be inefficient applied to a list as opposed to a vector. Dispatching on type, and using an intermediate vector to hold the contents of list can make both cases more efficient (since the array specific case can use aref
rather than elt
):
<lang lisp>(defun nshuffle (sequence)
(etypecase sequence (list (nshuffle-list sequence)) (array (nshuffle-array sequence))))
(defun nshuffle-list (list)
"Shuffle the list using an intermediate vector." (let ((array (nshuffle-array (coerce list 'vector)))) (declare (dynamic-extent array)) (map-into list 'identity array)))
(defun nshuffle-array (array)
(loop for i from (length array) downto 2 do (rotatef (aref array (random i)) (aref array (1- i))) finally (return array)))</lang>
D
This shuffles any collection that supports random access and defines length, the items must be copyable (such template constraints may be added to shuffle): <lang d>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]; shuffle(a); writeln(a);
} </lang> Knuth shuffle variant using the standard library: <lang d>import std.stdio, std.random;
void main() {
auto a = [1, 2, 3, 4, 5, 6, 7, 8, 9]; randomShuffle(a); writeln(a);
}</lang>
E
<lang e>def shuffle(array, random) {
for bound in (2..(array.size())).descending() { def i := random.nextInt(bound) def swapTo := bound - 1 def t := array[swapTo] array[swapTo] := array[i] array[i] := t }
}</lang>
<lang e>? def arr := [1,2,3,4,5,6,7,8,9,10].diverge()
- value: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].diverge()
? shuffle(arr, entropy) ? arr
- value: [4, 5, 2, 9, 7, 8, 1, 3, 6, 10].diverge()</lang>
Factor
There is a randomize
word already in the standard library. Implementation:
<lang factor>: randomize ( seq -- seq )
dup length [ dup 1 > ] [ [ iota random ] [ 1 - ] bi [ pick exchange ] keep ] while drop ;</lang>
Fantom
<lang fantom> class Main {
static Void knuthShuffle (List array) { ((array.size-1)..1).each |Int i| { r := Int.random(0..i) array.swap (i, r) } }
public static Void main () { List a := [1,2,3,4,5] knuthShuffle (a) echo (a)
List b := ["apples", "oranges", "pears", "bananas"] knuthShuffle (b) echo (b) }
} </lang>
Forth
<lang forth>include random.fs
- shuffle ( deck size -- )
2 swap do dup i random cells + over @ over @ swap rot ! over ! cell+ -1 +loop drop ;
- .array 0 do dup @ . cell+ loop drop ;
create deck 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,
deck 10 2dup shuffle .array</lang>
Fortran
<lang fortran>program Knuth_Shuffle
implicit none
integer, parameter :: reps = 1000000 integer :: i, n integer, dimension(10) :: a, bins = 0, initial = (/ (n, n=1,10) /)
do i = 1, reps a = initial call Shuffle(a) where (a == initial) bins = bins + 1 ! skew tester end do write(*, "(10(i8))") bins
! prints 100382 100007 99783 100231 100507 99921 99941 100270 100290 100442
contains
subroutine Shuffle(a)
integer, intent(inout) :: a(:) integer :: i, randpos, temp real :: r
do i = size(a), 2, -1 call random_number(r) randpos = int(r * i) + 1 temp = a(randpos) a(randpos) = a(i) a(i) = temp end do
end subroutine Shuffle
end program Knuth_Shuffle</lang>
F#
Allows a shuffle of arrays of arbitrary items. Requires 2010 beta of F#. Lazily returns a sequence.
This is the original Fisher-Yates shuffle as described by the link: <lang fsharp>open System
let FisherYatesShuffle (initialList : array<'a>) = // '
let availableFlags = Array.init initialList.Length (fun i -> (i, true)) // Which items are available and their indices let rnd = new Random() let nextItem nLeft = let nItem = rnd.Next(0, nLeft) // Index out of available items let index = // Index in original deck availableFlags // Go through available array |> Seq.filter (fun (ndx,f) -> f) // and pick out only the available tuples |> Seq.nth nItem // Get the one at our chosen index |> fst // and retrieve it's index into the original array availableFlags.[index] <- (index, false) // Mark that index as unavailable initialList.[index] // and return the original item seq {(initialList.Length) .. -1 .. 1} // Going from the length of the list down to 1 |> Seq.map (fun i -> nextItem i) // yield the next item
</lang> Here's the modified Knuth shuffle which shuffles the original array in place <lang fsharp>let KnuthShuffle (lst : array<'a>) = // '
let Swap i j = // Standard swap let item = lst.[i] lst.[i] <- lst.[j] lst.[j] <- item let rnd = new Random() let ln = lst.Length [0..(ln - 2)] // For all indices except the last |> Seq.iter (fun i -> Swap i (rnd.Next(i, ln))) // swap th item at the index with a random one following it (or itself) lst // Return the list shuffled in place</lang>
Example: <lang fsharp>> KnuthShuffle [| "Darrell"; "Marvin"; "Doug"; "Greg"; "Sam"; "Ken" |];; val it : string array = [|"Marvin"; "Doug"; "Sam"; "Darrell"; "Ken"; "Greg"|] </lang>
GAP
<lang 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)</lang>
Go
<lang go>package main
import (
"fmt" "rand" "time"
)
func main() {
var a [20]int for i := range a { a[i] = i } fmt.Println(a)
rand.Seed(time.Nanoseconds()) for i := len(a) - 1; i >= 1; i-- { j := rand.Intn(i + 1) a[i], a[j] = a[j], a[i] } fmt.Println(a)
}</lang>
Haskell
<lang 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))</lang>
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: <lang Haskell>knuthShuffleProcess :: (Show a) => [a] -> IO () knuthShuffleProcess =
(mapM_ print. reverse =<<). ap (fmap. (. zip [1..]). scanr swapElems) (mkRands. length)</lang>
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:
<lang haskell>import Data.Array.ST import Data.STRef import Control.Monad import Control.Monad.ST import Control.Arrow import System.Random
shuffle :: RandomGen g => [a] -> g -> ([a], g) shuffle list g = runST $ do
r <- newSTRef g let rand range = liftM (randomR range) (readSTRef r) >>= runKleisli (second (Kleisli $ writeSTRef r) >>> arr fst) a <- newAry (1, len) list forM_ [len, len - 1 .. 2] $ \n -> do k <- rand (1, n) liftM2 (,) (readArray a k) (readArray a n) >>= runKleisli (Kleisli (writeArray a n) *** Kleisli (writeArray a k)) liftM2 (,) (getElems a) (readSTRef r) where len = length list newAry :: (Int, Int) -> [a] -> ST s (STArray s Int a) newAry = newListArray</lang>
Icon and Unicon
The shuffle method used here can shuffle lists, record fields, and strings:
<lang icon>procedure main()
show(shuffle([3,1,4,1,5,9,2,6,3])) show(shuffle("this is a string"))
end
procedure shuffle(A)
every A[i := *A to 1 by -1] :=: A[?i] return A
end
procedure show(A)
every writes(!A," ") write()
end</lang>
Output:
->ks 9 6 1 4 3 1 3 5 2 i n t i s r t g h s a i s ->
Note that the gloriously succinct 'standard' Icon shuffle: <lang icon>procedure shuffle(A)
every !A :=: ?A
end</lang> is subtly biased.
J
<lang j>KS=:{~ (2&{.@[ {`(|.@[)`]} ])/@(,~(,.?@>:))@i.@#</lang> The input array is transformed to a rectangular array of indexes. By doing this all kinds of arrays can serve as input (see examples below). The process is imitated by using using a fold, swapping elements in a restricted part of this index-array in each fold step. <lang j>proces J
fold swap transform array <==> f / g y</lang>
Example of a transformed input: <lang j>(,~(,.?@>:))@i.@# 1+i.6 0 0 0 0 0 0 1 1 0 0 0 0 2 0 0 0 0 0 3 2 0 0 0 0 4 3 0 0 0 0 5 0 0 0 0 0 0 1 2 3 4 5</lang> The last row is the index-array that has to be shuffled. The other rows have valid indexes in the first two columns. The second column has a randomized value <= value first column.
The index-swapping is done by the part: <lang j>2&{.@[ {`(|.@[)`]} ]</lang> Finally, the shuffled indexes select elements from the original array. <lang j>input { ~ shuffled indexes</lang> Alternatively, instead of creating a rectangular array, the swapping indices and the original data can be individually boxed.
In other words, (,~ (,. ?@>:))@i.@#
can be replaced with |.@; ;&~./@(,. ?@>:)@i.@#
, and the swapping can be achieved using (<@C. >)/
instead of (2&{.@[ {`(|.@[)`]} ])/
.
With this approach, the data structure with the swapping indices and the original data could look like this:
<lang j> (|.@; ;&~./@(,. ?@>:)@i.@#)'abcde' +---+-+---+---+-+-----+ |4 2|3|2 1|1 0|0|abcde| +---+-+---+---+-+-----+</lang>
Note that we have the original data here, instead of indices to select all of its items. Note also that we have only a single value in a box where an item is being "swapped" with itself (this is required by J's cycle operation (C.
)).
The resulting definition looks like this:
<lang j>KS=: [: > (<@C. >)/@(|.@; ;&~./@(,. ?@>:)@i.@#)</lang>
Note that here we did not wind up with a list of indices which we used to permute the original data set. That data set is permuted directly. However, it is in a box and we do have to remove it from that box.
Permuting the data directly, instead of permuting indices, has performance implications when the items being swapped are large, but see the note at the end of this entry for J for how you would do this operation in a "real" J program.
Examples:<lang j>]A=: 5+i.9 5 6 7 8 9 10 11 12 13</lang> Shuffle: <lang j>KS A 13 10 7 5 11 9 8 6 12</lang>Input <lang j>]M=: /:~(1 2 3,:2 3 4),(11 2 3,: 0 11 2),(1 1 1,:1 0),:1 1 1,:1 0 1
1 1 1 1 0 0
1 1 1 1 0 1
1 2 3 2 3 4
11 2 3
0 11 2</lang>Shuffle
<lang j>KS M 11 2 3
0 11 2
1 1 1 1 0 1
1 1 1 1 0 0
1 2 3 2 3 4</lang>Input
<lang j>]L=:'aA';'bbB';'cC%$';'dD@' +--+---+----+---+ |aA|bbB|cC%$|dD@| +--+---+----+---+</lang>Shuffle <lang j>KS L +--+----+---+---+ |aA|cC%$|dD@|bbB| +--+----+---+---+</lang> In J the shuffling of an arbitrary array can easily be implemented by the phrase ( ref http://www.jsoftware.com/jwiki/JPhrases/RandomNumbers ): <lang j>({~?~@#)</lang> Applied on the former examples: <lang j>({~?~@#) A 8 7 13 6 10 11 5 9 12
({~?~@#) M 1 1 1 1 0 1
1 2 3 2 3 4
11 2 3
0 11 2
1 1 1 1 0 0
({~?~@#) L
+----+---+--+---+ |cC%$|bbB|aA|dD@| +----+---+--+---+</lang>
Java
<lang java>import java.util.Random;
public static final Random gen = new Random();
// version for array of ints public static void shuffle (int[] array) {
int n = array.length; while (n > 1) { int k = gen.nextInt(n--); //decrements after using the value int temp = array[n]; array[n] = array[k]; array[k] = temp; }
} // version for array of references public static void shuffle (Object[] array) {
int n = array.length; while (n > 1) { int k = gen.nextInt(n--); //decrements after using the value Object temp = array[n]; array[n] = array[k]; array[k] = temp; }
}</lang>
JavaScript
<lang 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]);
}</lang>
results in:
1,2,3 16619 1,3,2 16614 2,1,3 16752 2,3,1 16959 3,1,2 16460 3,2,1 16596
LabVIEW
Liberty BASIC
<lang lb>'Declared the UpperBound to prevent confusion with lots of 9's floating around.... UpperBound = 9 Dim array(UpperBound)
For i = 0 To UpperBound
array(i) = Int(Rnd(1) * 10) Print array(i)
Next i
For i = 0 To UpperBound
'set a random value because we will need to use the same value twice randval = Int(Rnd(1) * (UpperBound - i)) temp1 = array(randval) temp2 = array((UpperBound - i)) array(randval) = temp2 array((UpperBound - i)) = temp1
Next i
Print For i = 0 To UpperBound
Print array(i)
Next i</lang>
Logo
<lang logo>to swap :i :j :a
localmake "t item :i :a setitem :i :a item :j :a setitem :j :a :t
end to shuffle :a
for [i [count :a] 2] [swap 1 + random :i :i :a]
end
make "a {1 2 3 4 5 6 7 8 9 10} shuffle :a show :a</lang>
Lua
<lang 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</lang>
M4
<lang M4>divert(-1) define(`randSeed',141592653) define(`rand_t',`eval(randSeed^(randSeed>>13))') define(`random',
`define(`randSeed',eval((rand_t^(rand_t<<18))&0x7fffffff))randSeed')
define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`set',`define(`$1[$2]',`$3')') define(`get',`defn($1[$2])') define(`new',`set($1,size,0)') define(`deck',
`new($1)for(`x',1,$2, `set(`$1',x,x)')`'set(`$1',size,$2)')
define(`show',
`for(`x',1,get($1,size),`get($1,x)`'ifelse(x,get($1,size),`',`, ')')')
define(`swap',`set($1,$2,get($1,$4))`'set($1,$4,$3)') define(`shuffle',
`define(`s',get($1,size))`'for(`x',1,decr(s), `swap($1,x,get($1,x),eval(x+random%(s-x+1)))')')
divert
deck(`b',52) show(`b') shuffle(`b') show(`b')</lang>
Output:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 6, 22, 33, 51, 35, 45, 16, 32, 7, 34, 10, 44, 5, 38, 43, 25, 29, 9, 37, 20, 21, 48, 24, 46, 8, 26, 41, 47, 49, 36, 14, 31, 15, 39, 12, 17, 13, 1, 3, 4, 27, 11, 28, 2, 19, 30, 42, 50, 18, 52, 40, 23
Mathematica
Usage of built-in function: <lang Mathematica>RandomSample[{1, 2, 3, 4, 5, 6}]</lang> Custom function: <lang Mathematica>Shuffle[input_List /; Length[input] >= 1] :=
Module[{indices = {}, allindices = Range[Length[input]]}, Do[ AppendTo[indices, Complement[allindices, indices][[RandomInteger[{1, i}]]]]; , {i, Length[input], 1, -1} ]; inputindices ]</lang>
Example: <lang Mathematica>Shuffle[{1, 2, 3, 4, 5, 6}]</lang>
MATLAB
Because this shuffle is done using rounds of operations on subsets of decreasing size, this is not an algorithm that can be vectorized using built-in MATLAB functions. So, we have to go old-school, no fancy MATLAB trickery.
<lang MATLAB>function list = knuthShuffle(list)
for i = (numel(list):-1:2) j = floor(i*rand(1) + 1); %Generate random int between 1 and i %Swap element i with element j. list([j i]) = list([i j]); end
end</lang>
There is an alternate way to do this that is not a true Knuth Shuffle, but operates with the same spirit. This alternate version produces the same output, saves some space, and can be implemented in-line without the need to encapsulate it in a function call like the Knuth Shuffle. <lang MATLAB>function list = randSort(list)
list = list( randperm(numel(list)) );
end</lang>
Modula-3
<lang modula3>MODULE Shuffle EXPORTS Main;
IMPORT IO, Fmt, Random;
VAR a := ARRAY [0..9] OF INTEGER {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
VAR temp: INTEGER; n: INTEGER := NUMBER(a);
BEGIN
WITH rand = NEW(Random.Default).init() DO WHILE n > 1 DO WITH k = rand.integer(0, n - 1) DO DEC(n); temp := a[n]; a[n] := a[k]; a[k] := temp; END; END; END;
END Shuffle;
BEGIN
Shuffle(a); FOR i := FIRST(a) TO LAST(a) DO IO.Put(Fmt.Int(a[i]) & " "); END; IO.Put("\n");
END Shuffle.</lang> Output:
martin@thinkpad:~$ ./shuffle 9 2 7 3 6 8 4 5 1 10 martin@thinkpad:~$ ./shuffle 1 7 8 10 5 4 6 3 9 2
MUMPS
<lang MUMPS>Shuffle(items,separator) New ii,item,list,n Set list="",n=0 Set ii="" For Set ii=$Order(items(ii)) Quit:ii="" Do . Set n=n+1,list(n)=items(ii),list=list_$Char(n) . Quit For Quit:list="" Do . Set n=$Random($Length(list))+1 . Set item=list($ASCII(list,n)) . Set $Extract(list,n)="" . Write item,separator . Quit Quit CardDeck New card,ii,suite Set ii=0 For suite="Spades","Hearts","Clubs","Diamonds" Do . For card=2:1:10,"Jack","Queen","King","Ace" Do . . Set ii=ii+1,items(ii)=card_" of "_suite . . Quit . Quit Quit
Kill items Set items(91)="Red" Set items(82)="White" Set items(73)="Blue" Set items(64)="Yellow" Set items(55)="Green" Do Shuffle(.items," ") ; Red Yellow White Green Blue Do Shuffle(.items," ") ; Red Blue Yellow White Green Do Shuffle(.items," ") ; Green Blue Yellow White Red
Kill items Do CardDeck,Shuffle(.items,$Char(13,10)) Queen of Hearts 9 of Diamonds 10 of Hearts King of Hearts 7 of Diamonds 9 of Clubs 6 of Diamonds 8 of Diamonds Jack of Spades Ace of Hearts Queen of Diamonds 9 of Hearts 2 of Hearts King of Clubs 10 of Spades 7 of Clubs 6 of Clubs 3 of Diamonds 3 of Spades Queen of Clubs Ace of Spades 4 of Hearts Ace of Diamonds 7 of Spades Ace of Clubs King of Spades 10 of Diamonds Jack of Diamonds 8 of Clubs 4 of Spades Jack of Hearts 10 of Clubs 4 of Diamonds 3 of Hearts 2 of Diamonds 5 of Hearts Jack of Clubs 2 of Clubs 5 of Diamonds 6 of Hearts 4 of Clubs 9 of Spades 3 of Clubs 5 of Spades 6 of Spades 7 of Hearts 8 of Spades 8 of Hearts 2 of Spades Queen of Spades King of Diamonds 5 of Clubs</lang>
OCaml
<lang ocaml>let shuffle arr =
for n = Array.length arr - 1 downto 1 do let k = Random.int (n + 1) in let temp = arr.(n) in arr.(n) <- arr.(k); arr.(k) <- temp done</lang>
Oz
<lang oz>declare
proc {Shuffle Arr} Low = {Array.low Arr} High = {Array.high Arr} in for I in High..Low;~1 do
J = Low + {OS.rand} mod (I - Low + 1)
OldI = Arr.I in
Arr.I := Arr.J
Arr.J := OldI end end
X = {Tuple.toArray unit(0 1 2 3 4 5 6 7 8 9)}
in
{Show {Array.toRecord unit X}} {Shuffle X} {Show {Array.toRecord unit X}}</lang>
PARI/GP
<lang>FY(v)={
forstep(n=#v,2,-1, my(i=random(n)+1,t=v[i]); v[i]=v[n]; v[n]=t ); v
};
FY(vector(52,i,i))</lang>
Pascal
<lang Pascal>program Knuth;
const
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.</lang>
Sample output:
2 7 10 4 3 5 1 9 6 8
Perl
<lang perl>sub shuffle {
my @a = @_; foreach my $n (1 .. $#a) { my $k = int rand $n + 1; $k == $n or @a[$k, $n] = @a[$n, $k]; } return @a;
}</lang>
Perl 6
<lang perl6>sub shuffle (@a is copy) {
for 1 ..^ @a -> $n { my $k = (0 .. $n).pick; $k == $n or @a[$k, $n] = @a[$n, $k]; } return @a;
}</lang> The shuffle is also built into the pick method on lists when you pass it a "whatever" for the number to pick:
<lang perl6>my @deck = @cards.pick(*);</lang>
PHP
<lang php>//The Fisher-Yates original Method function yates_shuffle($arr){ $shuffled = Array(); while($arr){ $rnd = array_rand($arr); $shuffled[] = $arr[$rnd]; array_splice($arr, $rnd, 1); } return $shuffled; }
//The modern Durstenfeld-Knuth algorithm function knuth_shuffle(&$arr){ for($i=count($arr)-1;$i>0;$i--){ $rnd = mt_rand(0,$i); list($arr[$i], $arr[$rnd]) = array($arr[$rnd], $arr[$i]); } }</lang>
PicoLisp
<lang PicoLisp>(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)) ) ) ) ) )</lang>
PL/I
<lang 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; </lang>
PowerShell
<lang powershell>function shuffle ($a) {
$c = $a.Clone() # make copy to avoid clobbering $a 1..($c.Length - 1) | ForEach-Object { $i = Get-Random -Minimum $_ -Maximum $c.Length $c[$_-1],$c[$i] = $c[$i],$c[$_-1] $c[$_-1] # return newly-shuffled value } $c[-1] # last value
}</lang> This yields the values one by one instead of returning the array as a whole, so the rest of the pipeline can work on the values while shuffling is still in progress.
PureBasic
<lang PureBasic>Procedure KnuthShuffle (Array a(1))
Protected i, size = ArraySize(a()) For i = 0 To size Swap a(i), a(Random(size)) Next
EndProcedure
Procedure displayArray(Array a(1))
Protected i, size = ArraySize(a()) For i = 0 To size Print(Str(a(i))) If i = size Continue EndIf Print(", ") Next PrintN("")
EndProcedure
- NumElements = 20
Dim b(#NumElements - 1)
Define i For i = 0 To #NumElements - 1
b(i) = i
Next
If OpenConsole()
PrintN("Before shuffle:") displayArray(b()) KnuthShuffle(b()) PrintN("After shuffle:") displayArray(b()) Print(#CRLF$ + #CRLF$ + "Press ENTER to exit") Input() CloseConsole()
EndIf
</lang>
Sample output:
Before shuffle: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 After shuffle: 12, 2, 10, 4, 17, 7, 9, 14, 5, 1, 0, 16, 3, 11, 8, 18, 15, 13, 19, 6
Python
Python's standard library function random.shuffle
uses this algorithm and so should normally be used. The function below is very similar:
<lang python>from random import randrange
def knuth_shuffle(x):
for i in range(len(x)-1, 0, -1): j = randrange(i + 1) x[i], x[j] = x[j], x[i]
x = list(range(10)) knuth_shuffle(x) print("shuffled:", x)</lang> Sample output
shuffled: [5, 1, 6, 0, 8, 4, 2, 3, 9, 7]
R
See also, the built-in function 'sample'.
Original Fisher-Yates version <lang r>fisheryatesshuffle <- function(n) {
pool <- seq_len(n) a <- c() while(length(pool) > 0) { k <- sample.int(length(pool), 1) a <- c(a, pool[k]) pool <- pool[-k] } a
}</lang> Knuth variation: <lang r>fisheryatesknuthshuffle <- function(n) {
a <- seq_len(n) while(n >=2) { k <- sample.int(n, 1) if(k != n) { temp <- a[k] a[k] <- a[n] a[n] <- temp } n <- n - 1 } a
}
- Example usage:
fisheryatesshuffle(6) # e.g. 1 3 6 2 4 5 x <- c("foo", "bar", "baz", "quux") x[fisheryatesknuthshuffle(4)] # e.g. "bar" "baz" "quux" "foo"</lang>
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 ]
REXX
<lang 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' deck.1=' color joker' /*good decks have a color joker,*/ deck.2=' b&w joker' /* and a black & white joker.*/ cards=2 say '------------------ getting a new deck out of the box...'
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 end
call showDeck 'ace' say '------------------ shuffling' cards "cards..."
do j=cards by -1 to 1 rand=random(1,j) if rand\==j then do /*swap two cards in the deck.*/ _=deck.rand deck.rand=deck.j deck.j=_ end end
call showDeck say '------------------ ready to play schafkopf (take out jokers first).' exit
/*----------------------------------SHOWDECK subroutine-----------------*/
showDeck: parse arg break; say
do m=1 for cards if pos(break,deck.m)\==0 then say /*easier to read the cards. */ say 'card' right(m,2) deck.m end
say return </lang> Output:
------------------ getting a new deck out of the box... card 1 color joker card 2 b&w joker card 3 club ace card 4 club 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 spade king card 2 heart ace card 3 diamond duece card 4 club 6 card 5 diamond 5 card 6 diamond jack card 7 spade ace card 8 heart 4 card 9 diamond queen card 10 club 5 card 11 club 10 card 12 diamond ace card 13 heart queen card 14 heart 9 card 15 diamond 7 card 16 club king card 17 heart 7 card 18 club 4 card 19 club duece card 20 spade queen card 21 b&w joker card 22 diamond trey card 23 diamond 4 card 24 diamond 8 card 25 club jack card 26 club ace card 27 heart 6 card 28 heart 5 card 29 spade 10 card 30 heart 8 card 31 heart trey card 32 diamond 6 card 33 spade 6 card 34 club 7 card 35 spade 4 card 36 spade jack card 37 club trey card 38 club 9 card 39 club 8 card 40 spade 7 card 41 club queen card 42 heart king card 43 spade 9 card 44 spade duece card 45 heart duece card 46 diamond 10 card 47 diamond king card 48 heart 10 card 49 diamond 9 card 50 heart jack card 51 spade trey card 52 spade 5 card 53 spade 8 card 54 color joker ------------------ ready to play schafkopf (take out jokers first).
Ruby
<lang ruby>class Array
def knuth_shuffle! j = length i = 0 while j > 1 r = i + rand(j) self[i], self[r] = self[r], self[i] i += 1 j -= 1 end self end
end
r = Hash.new(0) 100_000.times do |i|
a = [1,2,3].knuth_shuffle! r[a] += 1
end
r.keys.sort.each {|a| puts "#{a.inspect} => #{r[a]}"}</lang> results in
[1, 2, 3] => 16572 [1, 3, 2] => 16610 [2, 1, 3] => 16633 [2, 3, 1] => 16714 [3, 1, 2] => 16838 [3, 2, 1] => 16633
More idomatic: <lang ruby>class Array
def knuth_shuffle! (length - 1).downto(1) do |i| j = rand(i + 1) self[i], self[j] = self[j], self[i] end self end
end</lang>
Scala
<lang Scala>def shuffle[T](a: Array[T]) = {
for (i <- 1 until a.size reverse) { val j = util.Random nextInt (i + 1) val t = a(i) a(i) = a(j) a(j) = t } a
}</lang>
Scheme
<lang scheme> (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 (shuffle vec)
(for ((i (in-range (- (vector-length vec) 1) 0 -1))) (let ((r (random i))) (swap vec i r))) vec)
</lang>
> (shuffle (list->vector (for/list ((i (in-range 0 12))) i))) #(11 9 7 5 10 6 2 0 1 3 8 4)
Smalltalk
<lang smalltalk>"The selector swap:with: is documented, but it seems not
implemented (GNU Smalltalk version 3.0.4); so here it is an implementation"
SequenceableCollection extend [
swap: i with: j [ |t| t := self at: i. self at: i put: (self at: j). self at: j put: t. ]
].
Object subclass: Shuffler [
Shuffler class >> Knuth: aSequenceableCollection [ |n k| n := aSequenceableCollection size. [ n > 1 ] whileTrue: [ k := Random between: 1 and: n. aSequenceableCollection swap: n with: k. n := n - 1 ] ]
].</lang>
Testing
<lang smalltalk>"Test" |c| c := OrderedCollection new. c addAll: #( 1 2 3 4 5 6 7 8 9 ). Shuffler Knuth: c. c display.</lang>
SNOBOL4
<lang SNOBOL4>* Library for random() -include 'Random.sno'
- # String -> array
define('s2a(str,n)i') :(s2a_end)
s2a s2a = array(n); str = str ' ' sa1 str break(' ') . s2a span(' ') = :s(sa1)f(return) s2a_end
- # Array -> string
define('a2s(a)i') :(a2s_end)
a2s a2s = a2s a ' ' :s(a2s)f(return) a2s_end
- # Knuth shuffle in-place
define('shuffle(a)alen,n,k,tmp') :(shuffle_end)
shuffle n = alen = prototype(a); sh1 k = convert(random() * alen,'integer') + 1
eq(a<n>,a<k>) :s(sh2) tmp = a<n>; a<n> = a<k>; a<k> = tmp
sh2 n = gt(n,1) n - 1 :s(sh1)
shuffle = a :(return)
shuffle_end
- # Test and display
a = s2a('1 2 3 4 5 6 7 8 9 10',10) output = a2s(a) '->' shuffle(a) output = a2s(a)
end</lang>
Sample Output:
1 2 3 4 5 6 7 8 9 10 -> 2 10 4 9 1 5 6 8 7 3
Tcl
<lang tcl>proc knuth_shuffle lst {
set j [llength $lst] for {set i 0} {$j > 1} {incr i;incr j -1} { set r [expr {$i+int(rand()*$j)}] set t [lindex $lst $i] lset lst $i [lindex $lst $r] lset lst $r $t } return $lst
}
% knuth_shuffle {1 2 3 4 5} 2 1 3 5 4 % knuth_shuffle {1 2 3 4 5} 5 2 1 4 3 % knuth_shuffle {tom dick harry peter paul mary} tom paul mary harry peter dick</lang> As a test of skewing (an indicator of a poor implementation) this code was used: <lang tcl>% for {set i 0} {$i<100000} {incr i} {
foreach val [knuth_shuffle {1 2 3 4 5}] pos {pos0 pos1 pos2 pos3 pos4} { incr tots($pos) $val }
} % parray tots tots(pos0) = 300006 tots(pos1) = 300223 tots(pos2) = 299701 tots(pos3) = 299830 tots(pos4) = 300240</lang>
TI-83 BASIC
Input L1, output L2.
:"SHUFFLE" :L1→L2 :dim(L2)→A :For(B,1,dim(L2)-1) :randInt(1,A)→C :L2(C)→D :L2(A)→L2(C) :D→L2(A) :A-1→A :End :DelVar A :DelVar B :DelVar C :DelVar D :Return
Ursala
This function works on lists of any type and length, including character strings.
<lang Ursala>shuffle = @iNX ~&l->r ^jrX/~&l ~&lK8PrC</lang>
test program: <lang Ursala>#cast %s
example = shuffle 'abcdefghijkl'</lang> output:
'keacfjlbdigh'
VBScript
Implementation
<lang vb> function shuffle( a ) dim i dim r randomize timer for i = lbound( a ) to ubound( a ) r = int( rnd * ( ubound( a ) + 1 ) ) if r <> i then swap a(i), a(r) end if next shuffle = a end function
sub swap( byref a, byref b ) dim tmp tmp = a a = b b = tmp end sub </lang>
Invocation
<lang vb> dim a a = array( 1,2,3,4,5,6,7,8,9) wscript.echo "before: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " ) wscript.echo "--" a = array( now(), "cow", 123, true, sin(1), 16.4 ) wscript.echo "before: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " ) shuffle a wscript.echo "after: ", join( a, ", " ) </lang>
Output
before: 1, 2, 3, 4, 5, 6, 7, 8, 9 after: 6, 4, 1, 2, 7, 3, 5, 8, 9 after: 8, 7, 3, 2, 6, 5, 9, 1, 4 -- before: 16/02/2010 5:46:58 PM, cow, 123, True, 0.841470984807897, 16.4 after: True, 16.4, 16/02/2010 5:46:58 PM, 123, cow, 0.841470984807897 after: 16.4, 16/02/2010 5:46:58 PM, 123, 0.841470984807897, True, cow
Vedit macro language
The shuffle routine in Playing Cards shuffles text lines in edit buffer. This example shuffles numeric registers #0 to #19.
The output will be inserted in current edit buffer.
<lang vedit>// Test main
- 90 = Time_Tick // seed for random number generator
- 99 = 20 // number of items in the array
IT("Before:") IN for (#100 = 0; #100 < #99; #100++) {
#@100 = #100 Num_Ins(#@100, LEFT+NOCR) IT(" ")
} IN
Call("SHUFFLE_NUMBERS")
IT("After:") IN for (#100 = 0; #100 < #99; #100++) {
Num_Ins(#@100, LEFT+NOCR) IT(" ")
} IN Return
//-------------------------------------------------------------- // Shuffle numeric registers #0 to #nn // #99 = number of registers to shuffle (nn-1) //
- SHUFFLE_NUMBERS:
for (#91 = #99-1; #91 > 0; #91--) {
Call("RANDOM") #101 = Return_Value #102 = #@101; #@101 = #@91; #@91 = #102
} Return
//-------------------------------------------------------------- // Generate random numbers in range 0 <= Return_Value < #91 // #90 = Seed (0 to 0x7fffffff) // #91 = Scaling (0 to 0x10000) //
- RANDOM:
- 92 = 0x7fffffff / 48271
- 93 = 0x7fffffff % 48271
- 90 = (48271 * (#90 % #92) - #93 * (#90 / #92)) & 0x7fffffff
Return ((#90 & 0xffff) * #91 / 0x10000)</lang>
Output:
Before: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 After: 9 13 8 18 10 1 17 15 0 16 14 19 3 2 7 11 6 4 5 12
- Programming Tasks
- Classic CS problems and programs
- Ada
- ALGOL 68
- AppleScript
- AutoHotkey
- BASIC
- Brat
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- E
- Factor
- Fantom
- Forth
- Fortran
- F Sharp
- GAP
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- LabVIEW
- Liberty BASIC
- Logo
- Lua
- M4
- Mathematica
- MATLAB
- Modula-3
- MUMPS
- OCaml
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PowerShell
- PureBasic
- Python
- R
- REBOL
- REXX
- Ruby
- Scala
- Scheme
- Smalltalk
- SNOBOL4
- Tcl
- TI-83 BASIC
- Ursala
- VBScript
- Vedit macro language