Does anyone here know how the sequence of songs is selected in Shuffle mode?
I have a Creative Labs ipod-substitute (although I think they had them before Apple) that I use at work. It has maybe 3000 songs on it, and I have it set to Shuffle mode.
What I hoped for in using Shuffle is that it would take all 3000 songs and establish a random play order for them, and then play them in that order continuously until I change the instructions, or set a new play order. That way, I wouldn’t hear the same song often enough to ever get tired of it and I wouldn’t have to hassle with putting new songs on or taking old songs off (the stuff I listen to is not contemporary, so I’m happy with the collection I have).
Instead of what I was hoping for, I might hear the same song twice in two or three days, and then hear a song I haven’t heard in months. It seems to randomly select a new song out of the list when each song ends. Also, I can go back to the previous song, but if I do that, and then go forward again to the “next” song, I get a different song than I started with (example: I start with song B, go back to song A, then go forward one song from A and end up at song M or something).
I have read the instruction manual, and it is unfortunately not instructive on this point.
Roddy
They probably won’t tell you, not because it’s some trade secret, but because nobody else really cares.
What they’re probably doing is taking your songs and numbering them 1 to 3000.
Then, when it’s time to move to a new song, they generate a random number (pseudorandom, most likely), and manipulate it to be within the range of 1-3000.
They also keep a pointer to the previous song, so you can go back.
What this means, is that if “Humpty Dance” is indexed as 373, if the random number generator comes up with 373, it gets played, regardless of how recently it’s been played.
If they have a good enough generator, it should be as infrequently as any other song, although with something like 3000 songs, you’ll see strange repeats unless you play through all 3000 many times.
The “shuffle” function in our RAV4 cycles through about a dozen sets of “random”. As in if you keep pressing shuffle to get a new song, you’ll only get a handful of different songs to begin with, and the “random” order of songs that plays after the first is always the same for any given push of “shuffle”. Next/Previous just goes to the current track +/-1… not randomly. This is especially annoying on MP3 discs with several hundred tracks, but can be a pretty efficient way to get around to a certain song rather than scrolling through the entire list of track.
I have a Samsung MP3 player, which has a very narrow view of shuffling, repeats within a few songs were common. When it played the same song twice in a row, out of possible selection of 600-700, I devised other methods of random.
I suspect the process is more along the lines of this:
Put all numbers from 1 to 3000 in order.
Randomly choose two of those numbers and swap them.
Repeat step 2 a large number of times.
Play files in the order of the now madly shuffled list.
The reason I think it’s like this, rather than generating a new pseudorandom number each time the Next key is pressed, is that my iPod Nano plays all songs in the same order until asked to shuffle songs again. I can go back/forward any number of songs and the order will never vary.
I have a Sony VAIO myself, and if I go back, then forward the shuffle will always go back to the original song. I can move back through the shuffled tracks pretty much indefinitely, and re-listen to exactly the same tracks in exactly the same order.
Also, it will play every song in the directory once before ever repeating (in fact, you have to use a special function for it to even repeat once it’s done playing all the songs in the directory). Like Dervorin, I strongly suspect it generates a random playlist first, then reads it in sequence.
There’s even a +/- system to weigh tracks so that they are more likely to come up soon or more often into a shuffle. Wonder how *that *works behind the screen…
I must admit however that I rarely use the shuffle on more than one album or one artist at a time, as full on randomization of over 30 gigs of music tends to spawn HorribleDJ2000, the evil bot that queues Cannibal Corpse right after Mozart. It hatessss your musssical sssssensssibilitiessss.
So I really don’t know how well that particular system handles longer lists - but it’s perfect for what I want it to do. Now if only ordering the files by artist & album in the first place wasn’t such a major PITA…
Kobal2, I had to do a weighted-random shuffle many years ago in a programming class. IIRC, the program maintained an array of weights, and picked a random number from 1 to the total of the weights. Then it would scan through the list, adding weights on the way, until the partial sum reached or passed the random number.
I suppose for a large list you could save all those additions with an index of partial sums and places to start adding. (“If random number > 100, start scanning from this song. If random number > 200, …”)
This is a pretty bad way of pre-generating a randomly ordered list of the numbers 1 to 3000… if the ‘large number’ isn’t large enough, then there’ll be a significant number that never got randomly chosen and are still in their original spot, (as well as those who just happened to randomly get swapped back to where they started.) and if the number of swaps is too high, then you’re just doing extra work.
I like the following:
Start a counter k at position 1 in the list
Generate a random number n from k (1) to 3000. If n = k, then leave the list exactly as it is, otherwise swap positions n and k
Advance k to 2, and follow the same step above, setting n to be a random number between 2 and 3000 inclusive. Keep going until k = 3000
Dervorin lists the most infamous way of (not) randomizing a list. And of course no Apple programmers would do that even if that was what they were trying to make a list.* chrisk’s method works correctly, but again, this is in no way how an iPod would actually shuffle. A list is complete waste of space.
All you need is a simple psuedo-random number generator. Start with a seed (generated each time to select “shuffle”), iterate for k cycles, there’s your k’th song. Trivial amount of storage. Can also go back a song by doing the k-1st cycles from start.
This also explains why some songs repeat more often than others. That’s because that’s the way an actual random device works. Do you really expect a dice rolled repeatedly won’t give you 2 fours before all the other numbers come up?
I’ve got a Creative Zen, too, and it’s random shuffle has been driving me crazy. It seems to weight songs by how recently they were played, so if I listen to a song a few times in one afternoon, it biases towards playing that. Sometimes it’s impossible to get it to cycle to any other than about four or five songs.
The truth is, I suspect many people don’t want a randomized playlist at all. Rather, they want songs to be added to a queue in random order, play the head of the queue, then remove the song!
I don’t think that works because that doesn’t guarantee that you’ll play all the songs before you start repeating them. I think some form of Dervorin’s scheme more likely.
Well, I’m not sure how your specific player does it, and it’s unlikely the company will ever tell, but here is how the open source music player Songbird shuffles its list. It boils down to the method Chrisk described (the memory requirement a playlist is trivial compared to that of a 4-minute pop song).
72 // Reserve space for return array
73 *aSequence = (PRUint32*)NS_Alloc(sizeof(PRUint32) * length);
74 *aSequenceLength = length;
75
76 // Reserve space for pool and sequence.
77 std::vector<PRUint32> pool;
78 pool.reserve(length);
79
80 // Generate pool.
81 for(PRUint32 current = 0; current < length; ++current) {
82 pool.push_back(current);
83 }
84
85 // Seed.
86 std::srand(std::clock());
87
88 // Randomly sample the pool to populate the sequence.
89 random_shuffle(pool.begin(), pool.end());
90
91 // Copy into the return array
92 copy(pool.begin(), pool.end(), *aSequence);
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& rand )
{
iterator_traits<RandomAccessIterator>::difference_type i, n;
n = (last-first);
for (i=2; i<n; ++i) swap (first*,first[rand(i)]);
}
Since this is a pretty standard C++ function, I wouldn’t be surprised if other Mp3 players operate in a similar manner.
Roderick Femm, stupid question: are you sure you’re not hitting the shuffle button again in between when you hear a song repeat? I own an iPod, and I know if choose shuffle, then decide I want to hear a specific song, when I hit shuffle a second time it is a new ordering of my songs, meaning I will hear “repeats.”
I have a Creative MP3 player here, and my explanation is going to be somewhat crazy.
It has something to do with the battery (Yes, your mild-manner AAA battery - at least my Mp3 Player is using it. Latest Creative models are chargable via USB ports, I think [I may be wrong])
Whenever I change the battery, the ‘current song’ is changed.
Let me rephrase this in a way that makes sense to me : adding one “point” to a song in the list creates a duplicate of that song in the list.
Meaning the partial sum goes 33 - song A, 34, song B, 35, song C, 36, song C again (weight 2), 37, song D etc…
Am I getting that right ?
In the case of my VAIO, that would explain how adding weight makes a given song more likely to pop up, but also why it’ll sometimes pop up multiple times in a single shuffle.
I bought a cheap stereo/single CD player for my bathroom around about the turn of the century and discovered that its random function is not particularly random at all. You put in a CD, you hit random, you hit play, and you always get the same “random” playlist (for example, I put in Radiohead’s OK Computer, and its always gonna be 4, 1, 12, 5, 2, 10, 3, etc.). If you hit stop, hit the random button twice to toggle it on and off, and hit play again, you get a different “random” playlist, but once again, its always the same playlist when you do exactly that sequence of button pushes.
My guess is that the random number seed is some value computed from the contents of the CD itself, and thus is always the same for the same CD. A “smarter” appliance either uses the current time, or if it doesn’t have an actual clock, the number of seconds the appliance has been turned on.
(Which I also reread. Okay, not an actual iPod. But this also happens with ours.)
And if you really want to avoid dups during a “cycle”, then you use a hash-like function. A simple map is to multiply the song’s index # by a prime number and take a mod. Not really pseudo-random of course.
