CODEWITHSUNDEEP
algorithmrandomshuffle
McDowells
McDowells

Reputation: 98

Efficient implementation of an iPod-like shuffle algorithm?

The goal is to pick a random song from 1..N with no repetitions for N songs, and be able to iterate forward and back like in an iPod. I used a hash table to store random songs. Is there a better way?

Upvotes: 2

Views: 370

Answers (2)

Bug Killer
Bug Killer

Reputation: 661

One way is to use an LCG based pseudo random number generator to choose songs. At every step song n+1 is (an+b)Mod 2^N. make sure that period of the LCG is above N. Iterate backwards using the inverse of the LCG

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372784

One simple algorithm for doing this would be to start off with a list of all N songs and then randomly shuffle the array elements using an algorithm like the Fisher-Yates Shuffle. Once you've done that, you will have an ordering of all the songs in a random order and with no duplicates. If you keep track of your current index in the list, you can then implement next and previous by just moving forwards or backwards in the array.

Hope this helps!

Upvotes: 4

Related Questions