Shuffle an array

From CodeCodex

The following implementations shuffle an array in-place:

Implementations[edit]

C++[edit]

#include <algorithm>

template <typename T>
void shuffle(T[] array, int len) {
  std::random_shuffle(array, array + len);
}

Erlang[edit]

shuffle(List) ->
    Random_list = [{random:uniform(), X} || X <- List],
    [X || {_,X} <- lists:sort(Random_list)].

Haskell[edit]

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

Java[edit]

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.

OCaml[edit]

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|]

OCaml : Array.sort[edit]

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|]

Perl[edit]

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 @_;
}

PHP[edit]

$numbers = range(1, 20);
shuffle($numbers);

Python[edit]

import random
l = range(10)
random.shuffle(l)

Ruby[edit]

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 (Later 1.8.7) 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]

Zsh[edit]

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
}