Searching \ for '[EE]: Shuffle algorithms...' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=shuffle+algorithms
Search entire site for: 'Shuffle algorithms...'.

Exact match. Not showing close matches.
PICList Thread
'[EE]: Shuffle algorithms...'
2002\10\14@042745 by Bill Westfield

face picon face
Request for comments:

============================================
I recently bought a bookshelf audio system with CD changer and MP3
capability.  I'm quite dissappointed in the MP3 capabilities; normal CD
functionality that becomes especially useful with large numbers of songs
available (ie a random shuffle capability) isn't present at all. :-( I
wondered why not, and decided that it's probably not a trivial thing to
produce a shuffled song list on a microcontroller with limitted memory.  On
a desktop computer, like a Mac or PC, MP3 players typically create nice
"play list" data structures, and to shuffle the list, you just assign a
random number to each item in the play list, and then sort by the random
number (un-sort?)  But those systems typically have Megabytes of memory
dedicated to the MP3 player, and processors with rather a lot of MIPS to do
the sorting.  The CD changer probably has a little 8bit microcontroller with
1k of RAM (or less), and sorting a list of a couple hundred songs in 1k of
RAM might be quite a challenge.

But there must be other ways to do it, I told myself.  You HAVE all the
songs out there on the CDs, you don't really need to maintain a separate
list of them in the microcontroller.  Just a "song number" would be enough.
And for that matter, you don't really need a LIST of the song numbers
(un-sorted or otherwise), you just somehow need to go through numbers from
1 to X in a random order.  Without repeating, of course.

This is a job for pseudo-random numbers, as produced by a shift registers
with XOR feedback on some of the bits.  Except...  Those produce the random
list we're looking for ONLY if N is a power of 2, in which case they produce
a sequence of all the numbers between 1 and 2^N-1, an a SINGLE apparently
random sequence. (the sequence is the same EVERY time.  If X follows Y the
first time, it will EVERY time.  Not so great for song lists!)  The modulous
operator is frequently used to reduce the range, but it tends to destroy the
"non-repeating" nature of the sequence, and sometimes patterns show up (much
to the dismay of many a game author.)

So we need some sort of mapping function that will map our range of 1..2^N
pseudo-random numbers into our range of 1..X different songs.  Without
causing repeats.  The simplest thing that comes to mind is to simply
THROW AWAY any numbers that are bigger than X...  In fact, this seems to
work pretty well - if N is large (16 bits) and X isn't, you can spend a
fair number of computer cycles throwing away numbers, but at modern
processor speeds you're not talking about a lot of time compare to seeking
and possibly switching a CD, so that's all right.  But this still leaves
use with only a single random sequence - we need an additional function to
give us more than one possible sequence.  There are a lot of possibilities
here - anything with mathematically unique results will do - but it seems
that SUBTRACTION (or addition) will work just fine...

So in pseudo C, we have:

       do {
          nextsong = pseudorandom() - offset;
       } while (nextsong > numberofsongs);

"offset" can be initialized to a real or somewhat real random number,
derived any way you like.  It controls which "region" of the PRN space we're
using, with a bit of additional effect when numbers pop into or out of the
relevant range.  pseudorandom() is a shift and xor PRN generator that has a
sequence length greater than numberofsongs  It's initial value can be random
as well, to change the starting point, but it's relatively unimportant since
we'll be using MOST of the PRN range anyway.

It's a piece of cake.  Every MP3 CD player ought to implement it.  Grr.

I have a real C "demo" version of this that lets you play with the numbers to
see how it behaves, if anyone is interested.  Checks for repetition, counts
the biggest spin loop, stuff like that...

Enjoy
BillW

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2002\10\14@080149 by Olin Lathrop

face picon face
> But there must be other ways to do it, I told myself.  You HAVE all the
> songs out there on the CDs, you don't really need to maintain a separate
> list of them in the microcontroller.  Just a "song number" would be
enough.
> And for that matter, you don't really need a LIST of the song numbers
> (un-sorted or otherwise), you just somehow need to go through numbers from
> 1 to X in a random order.  Without repeating, of course.

You've got two problems here:

1  -  Get a random number from 0 to N, where N is not limited to 2**M-1.

2  -  Get a different random sequence each time.

The first problem can be addressed in many ways.  For one method see the
RAND_MAX routine of the HAL PIC project at
http://www.embedinc.com/pic/hal.htm.  It finds the smallest 2**M-1, then
throws out random numbers > N.  The probability of needing to toss a number
is always less than 1/2.

To address the second problem, you need some sort of external information
that is not correlated to what the processor is doing.  This can be much
harder.  Random number generators in large computers often use the system
clock to initialize the random number seed.  At least this is guaranteed to
be different each time, although not truly random depending on use.  Perhaps
you could start timer 1 running at full speed at startup, then snapshot its
value on the first user interaction and use that as the random number
generator seed.  You have 66000 different possible sequences, selected by
the number of 200nS intervals between powerup and the first button press.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2002\10\14@082642 by Bob Ammerman

picon face
Here is a C-pseudocode implementation of a 'fair' shuffle algorithm. Each
song has an equal probability of appearing at a given place in the shuffle.

// Maximum songs to be supported
#define MAX_SONG    10        // or whatever # you want

// Array of song numbers
unsigned char  playlist[MAX_SONG];

// Helper function:

unsigned char get_random(unsigned char limit)
{
   return a random number in the range 0..limit
}

// Main shuffle function:

void shuffle(unsigned char nsongs)
{
   unsigned char i, j;
   unsigned char tmp;

   // Initialize the whole list to be in order
   for (i=0; i < nsongs; ++i)
       playlist[i] = i

   // Do the shuffle by swapping songs into
   // position working from the top down.
   for (i = nsongs-1; i>0; i--)
   {
       // the song for slot i should be randomly
       // chosen from the range 0..i
       j = get_random( i);

       // swap it in
       tmp = playlist[i];
       playlist[i] = playlist[j];
       playlist[j] = tmp;
   }
}

Note: The above may be counterintuitive, but with a little effort you can
see that it will generate a 'fair' shuffle, given a 'fair' random number
generator to start it.

Hint: what is the probability that a given song be the last song after the
shuffle. Then when that song has been assigned we reduce the problem by one
before assigning the next song.

This algorithm has the advantage of running in linear and deterministic time
(assuming the RNG does).


Bob Ammerman
RAm Systems



{Original Message removed}

2002\10\14@090235 by Wagner Lipnharski

flavicon
face
For the non-repetitive song in the shuffle list, with a limitted internal
RAM, it could use bits to identify songs.
Guessing that no one would store more than 320 songs (small ones) into a
700MB CD, 40 bytes would be enough for bit song ID list - To be played
bit=1, played drop the bit. For the random algorithm, probably measuring
the time between the "shuffle selection button" and "play button", and use
it as random seed - or, counting loops between power up and "play button".

Wagner Lipnharski - email:  spam_OUTwagnerTakeThisOuTspamustr.net
UST Research Inc. - Development Director
http://www.ustr.net - Orlando Florida 32837
Licensed Consultant Atmel AVR _/_/_/_/_/_/

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2002\10\14@130738 by Roman Black

flavicon
face
Wagner Lipnharski wrote:
>
> For the non-repetitive song in the shuffle list, with a limitted internal
> RAM, it could use bits to identify songs.
> Guessing that no one would store more than 320 songs (small ones) into a
> 700MB CD, 40 bytes would be enough for bit song ID list - To be played
> bit=1, played drop the bit. For the random algorithm, probably measuring


This is actually a standard system (marking off
played songs), but instead of selecting the song at
randown which requires a random number they just use
a prime number larger than half the playlist size.
Whenever it encounters a played song it advances
forward in the list to the next unplayed song.
Apparent randomness to the user is provided by simply
picking a song to start at. There are some other rules,
which I can't remember but I do remember the prime
number was used to eliminate the need to generate
a random number for each song. You are right that the
total ram cost should only be one bit per song.
-Roman

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2002\10\14@132401 by William Chops Westfield

face picon face
> Guessing that no one would store more than 320 songs (small ones) into a
> 700MB CD, 40 bytes would be enough for bit song ID list - To be played
> bit=1, played drop the bit. For the random algorithm, probably measuring

I have about 240 songs on one 650MB CD.  It's a 5-disk changer.  I don't
doubt that "marking off played songs" is a standard technique, but with over
1000 potential songs, this is probably precisely why the stupid player won't
shuffle the MP3s.  I expect there's something like an 8051, 6805, or PIC in
there, with "approx 256 bytes" of total RAM, most of it already in use
before the MP3 chip got added...  16 bits/song or even one byte/song is
probably quite impossible, and even 1bit/song (128+ bytes) is looking like
more memory than there is...

It would be interesting to look at the source code for such a box; I don't
suppose that any has been (legally) published?

BillW

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2002\10\14@152439 by Peter L. Peres

picon face
On Mon, 14 Oct 2002, William Chops Westfield wrote:

*>> Guessing that no one would store more than 320 songs (small ones) into a
*>> 700MB CD, 40 bytes would be enough for bit song ID list - To be played
*>> bit=1, played drop the bit. For the random algorithm, probably measuring
*>
*>I have about 240 songs on one 650MB CD.  It's a 5-disk changer.  I don't
*>doubt that "marking off played songs" is a standard technique, but with over
*>1000 potential songs, this is probably precisely why the stupid player won't
*>shuffle the MP3s.  I expect there's something like an 8051, 6805, or PIC in
*>there, with "approx 256 bytes" of total RAM, most of it already in use
*>before the MP3 chip got added...  16 bits/song or even one byte/song is
*>probably quite impossible, and even 1bit/song (128+ bytes) is looking like
*>more memory than there is...

Actually you only need to store the state of the random generator not the
whole list of songs. No ?

Peter

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2002\10\14@162313 by Wagner Lipnharski

flavicon
face
Peter L. Peres wrote:
> On Mon, 14 Oct 2002, William Chops Westfield wrote:

> Actually you only need to store the state of the random generator not
> the whole list of songs. No ?
>

Only if you can ensure the random generator will not repeat previous
numbers.

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2002\10\15@030154 by dr. Imre Bartfai

flavicon
face
Hi,

a good shuffle algorithm is also shown in Knuth's "The Art of Computer
Programming", Volume II. If interested, I could dig it.

Regards,
Imre


+-----------------------------------------------------------------------+
| The information transmitted is intended only for the person or entity |
| to which it is addressed and may contain confidential and/or          |
| privileged material.  Any review, retransmission, dissemination or    |
| other use of, or taking of any action in reliance upon, this          |
| information by persons or entities other than the intended recipient  |
| is prohibited. If you received this in error, please contact the      |
| sender and delete the material from any computer.                     |
+-----------------------------------------------------------------------+

On Mon, 14 Oct 2002, Bob Ammerman wrote:

{Quote hidden}

> {Original Message removed}

2002\10\15@035635 by Alan B. Pearce

face picon face
>I have about 240 songs on one 650MB CD.  It's a 5-disk
>changer.  I don't doubt that "marking off played songs"
>is a standard technique, but with over 1000 potential songs,
.....
>before the MP3 chip got added...  16 bits/song or even one
>byte/song is probably quite impossible, and even 1bit/song
>(128+ bytes) is looking like more memory than there is...

sounds like a case to put a small external FRAM chip on I2C or similar
interface to hold the "played list". Imagine having the power supply go
down, and still not hear a song repeated until all songs had been played
once :)))

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


More... (looser matching)
- Last day of these posts
- In 2002 , 2003 only
- Today
- New search...