Just thought I'd post this here as it's very nifty and very quick.
If you have a list of items (either an array or some other sort of ordered list) and you want to randomly shuffle them then this is a very cool tool.
First set up the ordered list (e.g. [1, 2, 3, 4, 5, 6]).
int i = size of array.
Then loop as follows for i > 1.
generate random number from 1 to i.
take this random entry from the list and swap with the number in ith place.
subtract 1 from i.
As an example...
 | | |
| Code: i list [1 2 3 4 5 6] 3 [1 2 6 4 5 3] 4 [1 2 6 5 4 3] 2 [1 5 6 2 4 3] 3 [1 5 6 2 4 3] 1 [5 1 6 2 4 3] | |
| | |
Starting list is [1 2 3 4 5 6] ending list is [5 1 6 2 4 3].
Using this method only requires one iteration per member in the list (i.e. it is linear).
It also guarantees that there will be no duplicates in the randomised list.
You may have already known this but I only discovered it yesterday so I though I'd share.