The Knuth shuffle algorithm is fast and easy. From Wikipedia:

"...the Knuth shuffle or Fisher-Yates shuffle[1], is a linear-time
algorithm (as opposed to the previous O(n log n) algorithm if using
efficient sorting such as mergesort or heapsort) which involves moving
through the pack from top to bottom, swapping each card in turn with
another card from a random position in the part of the pack that has
not yet been passed through (including itself). Providing that the
random numbers are unbiased, this will always generate a random
permutation.

"Notice that great care needs to be taken in implementing the Knuth
shuffle; even slight deviations from the correct algorithm will
produce biased shuffles. For example, working your way through the
pack swapping each card in turn with a random card from any part of
the pack is an algorithm with nn different possible execution paths,
yet there are only n! permutations. A counting argument based on the
pigeonhole principle will clearly show that this algorithm cannot
produce an unbiased shuffle, unlike the true Knuth shuffle, which has
n! execution paths which match up one-to-one with the possible
permutations."

http://en.wikipedia.org/wiki/Shuffle#Shuffling_algorithms

Cheers,
Zik

On 12/06/06, Phil Keller <Phil@pkeller.net> wrote:
> All,
>
>   I have an application that I need to generate a random number sequence
> for.  Not just a random number, I know how to do that, but an entire
> pseudo random sequence.  The sledge-hammer approach would be to generate
> a random number, see if it is already in the sequence and store it if it
> is new, then generate a new random number.  Early in the process this
> would work OK, but when I need the last four numbers the time required
> to generate the numbers could be excessive to say the least.
>
> The details:
> -    The user will have a random number of sound files (2 to 127) on a
> memory card.
> -    The PIC will count the number of available files and create a
> random number sequence that is non-repeating and inclusive of all file
> numbers.  (Each file is assigned a number so that I don't need to
> 'shuffle' the file names, just the numbers.)  I can skip files numbers
> that are greater than the number available but a sequence that stops at
> the maximum would be nice.
> -    The PIC will select the first file number and send the file to a
> player.
> -    Once that file is played the PIC will select the next file number
> in the sequence and send it to the player.
> -    Once all songs have been played once, the PIC will generate a new
> random sequence and start over.
>
>   Suggestions or pointers are greatly appreciated.
>
> Phil
>
>
> --
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist