Creating unbiased random permutations of lists is often crucial to sampling. The Fisher-Yates shuffle is the definitive method to shuffle a sequence of items. Popularised by Knuth, it is unbiased, has optimal linear time efficiency; uses constant space; and is incremental.   The modern Fisher-Yates algorithm is both elegant in its design and efficient at run-time.  Although it looks stunningly simple, this algorithm is unbiased, uses constant memory as it does in-place shuffling, and has optimal linear time efficiency In pseudo-code, it is simply: — To shuffle an array a of n elements (indices 0..n-1): for i from n−1 downto 1 do j ← random integer such that 0 ≤ j ≤ i exchange a[j] and a[i]   Discussion Despite its simplicty, when developers attempt to code this from scratch it is extremely common that they make ‘off by one’ errors, which results in a notably biased permutation. Most notably, it is of critical importance to note that in the correct implementation, it is possible that an item is to be ‘swapped with itself.’ (that is, $j=i$). Click here to see the definitive video explanation of the Fisher-Yates by Prof Sedgewick . Note that Sedgewick is the author of one of the most readable and respected books on this topic! Over 900 pages of amazing content all for free! Course: http://ow.ly/nKvN50lWAvj  PDF: http://ow.ly/lTG650lWAvk  Code: http://ow.ly/oQvD50lWAvm  Solutions: http://ow.ly/OcOg50lWAvl                            Code Thanks to the Rosetta code, here is the modern Fisher-Yates algorithm in some of the common languages. (Note that if the language has an internal shuffle, this is typically mentioned first. Even though it is obviously preferable to use internal shuffling if its available, it is still very illuminating to see how the modern Fisher-Yates algorithm could be implemented in your language of choice.   C++ #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 } #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); } } } 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; } } JavaScript (ES5) function knuthShuffle(arr) { var rand, temp, i;   for (i = arr.length – 1; i > 0; i -= 1) { rand = Math.floor((i + 1) * Math.random());//get random between zero and i (inclusive) temp = arr[rand];//swap i and the zero-indexed number arr[rand] = arr[i]; arr[i] = temp; } return arr; }   var 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 (var i = 0; i < 100000; i++) { res[knuthShuffle([1,2,3]).join(‘,’)] += 1; }   for (var key in res) { print(key + “\t” + res[key]); } Mathematica RandomSample[Range[n]] 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]] ]   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 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) 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 } *** My name is Martin Roberts. I have a PhD  in theoretical physics. I love maths and computing. I’m open to new opportunities – consulting, contract or full-time – so let’s have a chat on how we can work together! Come follow me on Twitter: @Techsparx! My other contact details can be found here. [mc4wp_form id=”1021″] Other Posts you may like The Unreasonable Effectiveness of Quasirandom Sequences Trigonometry in Pictures Evenly Distributing points in a triangle Evenly distributing points on a sphere