Algorithm to generate random order of elements

Question

How to randomize order of approximately 20 elements with lowest complexity? (generating random permutations)

Answer 1

Some months ago I blogged about obtaining a random permutation of a list of integers. You could use that as a permutation of indexes of the set containing your elements, and then you have what you want.

• Generating random int list in F#

• Uniformly distributed random list permutation in F#

In the first post I explore some possibilities, and finally I obtain "a function to randomly permutate a generic list with O(n) complexity", properly encapsulated to work on immutable data (ie, it is side-effect free).

In the second post, I make it uniformely distributed.

The code is in F#, I hope you don't mind!

Good luck.

EDIT: I don't have a formal proof, but intuition tells me that the complexity of such an algorithm cannot be lower than O(n). I'd really appreciate seeing it done faster!

Answer 2

A simple way to randomise the order is to make a new list of the correct size (20 in your case), iterate over the first list, and add each element in a random position to the second list. If the random position is already filled, put it in the next free position.

I think this pseudocode is correct:

list newList
foreach (element in firstList)
    int position = Random.Int(0, firstList.Length - 1)
    while (newList[position] != null)
     position = (position + 1) % firstList.Length
    newList[position] = element

EDIT: so it turns out that this answer isn't actually that good. It is neither particularly fast, nor particularly random. Thankyou for your comments. For a good answer, please scroll back to the top of the page :-)

Answer 3

Probably someone already implemented the shuffling for you. For example, in Python you can use random.shuffle, in C++ random_shuffle, and in PHP shuffle.

Answer 4

Knuth's shuffle algorithm is a good choice.