Shuffle an array
From CodeCodex
The following implementations shuffle an array in-place:
Contents |
[edit] Implementations
[edit] C++
#include <algorithm>
template <typename T>
void shuffle(T[] array, int len) {
std::random_shuffle(array, array + len);
}
[edit] Haskell
import System.Random
import Data.Array.MArray
shuffle :: (MArray a t IO, Random i, Ix i) => a i t -> IO ()
shuffle arr = do
r <- getBounds arr
forM_ (range r) $ \i -> swap i =<< randomRIO (0,i)
where swap i j = do
t <- readArray arr i
writeArray arr i =<< readArray arr j
writeArray arr j t
[edit] Java
import java.util.Arrays;
import java.util.Collections;
public class ArrayTools {
public static void shuffle(Object[] array) {
Collections.shuffle(Arrays.asList(array));
}
}
Adding Generics doesn't add any type-checking benefit in this case, so it is not used here.
[edit] OCaml
First define a function to swap two elements in an array:
# let swap a i j =
let t = a.(i) in
a.(i) <- a.(j);
a.(j) <- t;;
val swap : 'a array -> int -> int -> unit = <fun>
Then define a function to shuffle an array by swapping each element with a randomly chosen element:
# let shuffle a =
Array.iteri (fun i _ -> swap a i (Random.int (i+1))) a;;
val shuffle : 'a array -> unit = <fun>
For example:
# let a = Array.init 10 (fun i -> i);; val a : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|] # shuffle a; a;; - : int array = [|6; 7; 0; 8; 3; 2; 4; 9; 5; 1|]
[edit] OCaml : Array.sort
Warning: this is not a uniform shuffle. Not all permutation are equally likely.
Another solution is to use the function Array.sort from the standard OCaml library. This function works in the same way than the C function qsort() from its stdlib.h, that is a callback is used to compare two entries a and b of the array, this function should return a signed integer, an integer of 0 means that (a = b), a positive integer means that (a > b), and a negative integer means (a < b).
Here we just have to return randomly 1, 0 or -1:
# Random.self_init();; (* initialize the random generator *) - : unit = () # let shuffle = Array.sort (fun _ _ -> (Random.int 3) - 1) ;; val shuffle : '_a array -> unit = <fun> # let a = Array.init 10 (fun i -> i);; val a : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|] # shuffle a; a;; - : int array = [|2; 5; 7; 8; 4; 6; 3; 1; 9; 0|]
[edit] Ruby
class Array
def shuffle!
size.downto(1) { |n| push delete_at(rand(n)) }
self
end
end
Original source: [1]
Or even nicer (but less efficient):
class Array
def shuffle
sort_by { rand }
end
def shuffle!
self.replace shuffle
end
end
Or in newer versions of ruby "shuffle" is a built-in method
x = [1,2,3,4,5,6,7,8,9] x.shuffle #produced [9, 1, 7, 4, 6, 2, 3, 5, 8]
[edit] Perl
List::Util is included with Perl 5.005 thru 5.8 and beyond.
use List::Util qw(shuffle);
print join(", ",shuffle(0..100)),$/;
Or the long way
sub shuffle {
for my $i (0..$#_) {
my $j = rand($i + 1);
($_[$i],$_[$j]) = ($_[$j],$_[$i])
}
return @_;
}
[edit] PHP
[edit] Python
import random l = range(10) random.shuffle(l)
[edit] Zsh
Tested in zsh 4.3.2
function shuffle {
RANDOM=$$
local array shuffled size count index
integer size count index
typeset -a array shuffled
array=(${=*}) # Limited to 32767 elements because $RANDOM.
size=${(w)#array}
while ((count++ < size))
do
index=$((1 + (${(w)#array} * RANDOM / 32767)))
shuffled+=($array[$index])
array[$index]=()
done
}
Or
function fisher-yates {
zmodload zsh/mathfunc
typeset -a array swap
integer n k
array=(${=*})
n=${(w)#array}
for ((n += 1 ; n > 0 ; n--))
do
((k = 1 + int(rand48() * n)))
swap=($array[k])
array[k]=$array[n]
array[n]=$swap
done
}
