OddThinking

Here is an algorithm in O(n*f) time, where n is the number of slots and f is the number of feeds. It is possibly only an approximation, but it should rule out anything really bad and give very consistent results.

(1) Find the feed with the largest number of shows
(2) Distribute the feed uniformly among the remaining slots in chronological order within the feed.
(3) Repeat

Using your original wine-gum example with the following feeds and counts:

R: 3
L: 3
O: 6
I: 2

So we start out with 14 remaining slots (0-based) and O as the largest feed with 6 shows. Each show goes in slot floor((14/6)*k)-1 where k = [1,6]. So the 6 shows are at slots 1, 3, 6, 8, 10, 13.

Now we have 8 remaining slots and pick R with 3 shows. Each show goes in the free slot floor((8/3)*k)-1 where k = [1,3]. To find a free slot , we have to iterate over the list of slots and skip any that are in use. So the 3 shows are at slots 2 (free slot #1), 7 (free slot #5), and 12 (free slot #7).

And so on.

It does have the peculiarity of having the rarest feed first. If you want the least rare feed first, reverse the order or let k be from 0 to feedSize – 1. I *think* that randomizing the order of feeds put int o the algorithm should not affect the distribution but I can’t think of a proof off hand. Is this a sufficient solution?

Whoops. There is a typo in my example. When distributing the ‘R’ feed, the second show should be at slot 5 (free slot #4).

-D

Julian,

I can’t quite understand why you seem so determined to work within the limitations of your hardware, instead of finding a device which can provide the flexibility you seem to want. In other words a device with a display and controls to allow you to pick whatever song/podcast you want to listen to next.

In this vein, you might also want to re-state your objections to using iTunes. Frankly, they come off as a bit petulant and whiny. Is a non-native-Windows UI really that much of a show-stopper? Can’t you just use it anyway? Grit your teeth, think of England, whatever it takes?

A new MP3 player with controls and display is what … a couple of hundred buck at the most? Surely this is an easy expenditure to justify over all this coding effort you’re expending, unless you’re mainly interested in the algorithmic solution and associated blog fodder. (And it is interesting).

In which case I would have to say I prefer Jonathon’s algorithm to yours; mainly on the basis of simplicity. To be honest I don’t quite follow yours.

I don’t believe Julian is mainly interested in the algorithmic solution and associated blog fodder. I think he is highly interested in those things, but probably is most interested in having some automated way to gather and spread out the feeds so that he doesn’t have to select them manually, either beforehand or during listening. If only there were an MP3 player which provided “chronological wine-gum algorithm” shuffling, rather than purely random, my guess is that he’d jump on it.

I also like Jonathon’s algorithm for its simplicity. It almost feels too simple, and perhaps Julian will find something undesirable about it (even besides being insufficiently complicated to make a decent blog entry or take up enough coding time and effort); I’ve yet to play with it or with Julian’s own algorithm.

Finally, in my typical pedantic fashion, I would like to point out that every tree (in this context) is a graph.

I love getting such thoughtful comments! Thank you. That they shoot my post full of holes and force me to re-think some ideas only makes them better! 🙂

Let’s start with Jonathon’s algorithm.

It is possibly only an approximation

I think that is easy to prove with a simple example.

With R:2, O:1 and L:1, this algorithm will find the answer “R-O-R-L”, where a better answer is “R-O-L-R”.

should rule out anything really bad and give very consistent results

I agree.

Is this a sufficient solution?

That’s a very hard question to answer.

It is obviously much faster than an implementation that seeks the full solution.

I proposed another (also suboptimal) solution at the bottom of the original post, involving horizontal lines.

I think the algorithm described there will give slightly better results than Jonathan’s, and I think that algorithm is O(n*log(n)), which is probably pretty close to O(n*f), so equivalent to Jonathon’s.

There’s an even easier approximate solution is O(n). However, it sometimes performs very badly. Simply select from a random feed is weighted towards the size of the remaining feeds. (The O(n) assumes rand(n) is constant time.)

So the question is how do I compare a bad O(n) heuristic against a better O(n*f) heuristic against an unknown quality, unknown complexity heuristic against an O(n!) perfect solution?

Answer: I dunno, but Alastair’s argument of choosing simplicity is a pretty damn strong one. If I was leading a project team doing this for commercial software, I would tell the team to use Jonathon’s solution; it’s both simple and right enough. Luckily, for me, for my private hacking, I get to implement it the hard, fun way!

I can’t quite understand why you seem so determined to work within the limitations of your hardware, instead of finding a device which can provide the flexibility you seem to want. In other words a device with a display and controls to allow you to pick whatever song/podcast you want to listen to next.

When I am listening on my computer, I do choose exactly which song or podcast I want to listen to next. In the case of podcasts, I delete them immediately after I hear them.

When I am listening in my car, I have an MP3 CD player that has a display. If I am listening to music, I can select the songs or folders I want to listen to, as often as I want to listen to them. When I am listening to podcasts, I only want to hear each one once, and I don’t want to have to keep track of which ones I have already heard, so I want the order to be pre-determined. It isn’t about a lack of display; it is about the lack of a method to flag/delete a podcast I have heard.

When I listen to MP3s on my iPod Shuffle, I have less choice. Another MP3 player would give me more choice, but the itsy-bitsy form-factor of the iPod Shuffle is more important to me than the lack of display. The new iPod Nano may change my decision here! I am not sure if the iPod Nano would give me the ability to quickly flag/delete a podcast immediately after I have listened to it.

As for iTunes, using it makes me feel stupid. I don’t like that. If I was being paid to use it, I would indeed lie back and think of England. If it had unique features that required the unexpected UI, I might try to embrace its differences. However, given that it has so many competitors for playing music, I don’t feel the need to use it for that. Given it can’t download and shuffle with a “stable sort” for podcasts from the same feed, I don’t want use it for downloading.

I’ll concede it’s probably petulant and whiny to mention it all in the post above; perhaps I should have just let the matter drop, but I still defend my choice to not use it.

Finally, in my typical pedantic fashion, I would like to point out that every tree (in this context) is a graph.

You are, of course, absolutely right. I should have said “It is only a tree, not an arbitrarily connected graph.” The problem was that I was having to come up with method that would return a unique node id, so that the argorithm could detect when it had already visited a node. However, that would never happen, so I didn’t need to implement such a check.

With R:2, O:1 and L:1, this algorithm will find the answer “R-O-R-L”, where a better answer is “R-O-L-R”.

That’s easy enough to fix: instead of distributing completely uniformly, always put the last item in the last available slot and then distribute uniformly. That will stretch the items of each feed as far apart as possible.

Here’s an implementation.

#!/usr/bin/perl
use strict;
use warnings;
use List::Util 'sum';
 
my %feed_item_count = @ARGV;
 
my $total_slots = sum values %feed_item_count;
my @available_slot = ( 0 .. $total_slots - 1 );
 
my @slot_item;
 
for my $feed ( sort { $feed_item_count{$b} <=> $feed_item_count{$a} } keys %feed_item_count ) {
    $slot_item[ pop @available_slot ] = $feed;
 
    my $count = $feed_item_count{ $feed } - 1;
    my @idx = map { $_ * @available_slot / $count } 0 .. $count - 1;
 
    @slot_item[ @available_slot[ @idx ] ] = ( $feed ) x @idx;
 
    delete @available_slot[ @idx ];
    @available_slot = grep { defined } @available_slot;
}
 
print "@slot_item\n";

Call it by passing pairs of feed names and item counts on the command line, eg. perl winegum.pl R 3 L 3 O 6 I 2

Aristotle,

It’s fast, it’s simple but it still isn’t optimal.

If you pass the parameters R 2 O 2, you get O-R-R-O instead of O-R-O-R.

No one claimed it’s optimal. The strategy will clearly produce degenerate results for a population consisting mostly or entirely of two-item feeds simply because of the placement strategy. The pattern you see will simply expand: A-B-C-D-E-F-G-G-F-E-D-C-B-A.

Now how problematic is that degenerate case really?

It seems to me that it’s really only an issue for the middlemost four slots that end up being A-B-B-A. If that bothers you so much, it is easy to add a post-processing step with keyhole optimisation type fix for this. (Actually you probably want to look for A-B-C-C-B-A first because turning that into A-B-C-A-B-C is sufficiently better than turning it into A-B-C-B-C-A to make it worth the effort. Beyond 6 slots, the returns diminish rapidly.)

Hmm, it strikes me that you really want to model this sort of in terms of fluid dynamics.

We consider each item piece to repel items from its own feed, with a force inversely proportional to some function of the distance – probably its square. You start with a system with randomly ordered items, and simply calculate the forces on each of the items, then swap neighbouring items where the directed force on one of the items minus the directed force on the other is greater than a certain threshold. Said threshold represents friction. Then you just iterate until the system reaches an equilibrium.

This won’t find optimal solutions either, because when the available space is much larger than a particular population of items, the fall-off of the force at a distance means they won’t repel each other strongly enough to spread across the entire available space. But the items will pull so far apart anyway that for the stated purpose of the algorithm (you don’t want to hear items from the same feed too frequently), it just doesn’t matter.

Julian, I am equally bothered by a lack of an optimal solution. However I don’t think that the problem is NP-complete. One of the problems is that the metric for success is still poorly defined. You are not seeking to maximize the average distance between two of the same feed. Rather you are trying to maximize the minimum distance between two of the same feed. And minimize the number of instances of the minimum-distance. This is a much more complicated metric.

Part of my thought in trying to come up with an optimal solution was focussed on greedy/iterative algorithms. I tried to come up with an algorithm which was given an optimal sub-sequence and which added a show to the end which also yielded an optimal sub-sequence. I hoped by this to have an inductive proof of optimality. Unfortunately, this entire class of solutions is impossible because optimal sequences can contain non-optimal sub-sequences. Optimality being defined here as having every permutation result in a lower or equal minimum-distance. For instance, take R-3, B-1, G-1. One optimal arrangement is RBRGR. But the sub-sequence RBRG is not an optimal sub-sequence since within that sub-sequence RBGR is a better permutation. So no solution based on an inductive proof is possible.

I’ll let you know if I come up with something positive.

fluid dynamics

Sounds cool! Perhaps a bit complicated, but cool.

I am already imagining prototypes models of winegums attached to springs!

One of the problems is that the metric for success is still poorly defined.

Really? I thought it was reasonably well defined back in the comments on the original wine-gum post. Do you disagree?

Rather you are trying to maximize the minimum distance between two of the same feed. And minimize the number of instances of the minimum-distance.

The metric that I am explicitly trying to maximise is the product of the distances between every two consecutive instances of the same feed.

If you are arguing that I should change my metric for better listening pleasure, I am open to it.

I actually suspect that the product of the square roots of the distances might be more accurate to reality. However, it would probably take me half-an-hour just to come up with an example where the difference in metrics would change the outcome, so I haven’t bothered.

Unfortunately, this entire class of solutions is impossible because optimal sequences can contain non-optimal sub-sequences.

That is an insightful way to look at it! You’ve proved we can’t produce a short-sighted algorithm that incrementally adds another wine-gum to the end of the sequence without considering all of the remaining colours.

Complicated? Algorithmically it’s very simple – much easier to conceptualise than the code for any solution involving backtracking, as far as I’m concerned. It’s a bit costly in that calculating all the forces during an iteration is O(n²) – but your playlists shouldn’t be large enough to make that a problem, and if they are, you can cut off at a fixed distance, since the distance fall-off and friction threshold conspire to make the forces from distant items irrelevant. (In a universe as small as yours and with only one dimension, anyway – in the cosmos, the sheer amount of gravitating mass can make the forces of even hugely distant objects significant. We have a rendezvous with Andromeda in about 3bn years.)

Perhaps I misunderstand the dilemma, but it strikes me that if you’re using any form of graph-search algorithm (ie: A* or BFS, the two you mention), you will only get the optimal solution if your metric (a.k.a. heuristic) underestimates the true solution. That is, the algorithm tries to achieve something it can’t possibly reach, and gets closer and closer to the optimal solution. If the metric ever overestimates (and it’s not clear to me whether yours does or doesn’t, because I can’t figure out the “true” metric), then you won’t get the optimal solution.
It is however 12:07am, so take this comment with appropriate time dilation accounted for…

Tom,

Yes, you are right. In the traditional description of the shortest-path algorithms, the heuristic is an under-estimate (or more strictly, never an over-estimate) of the final path length.

Because I am seeking to maximise a metric, rather than (as is more traditional) minimise a path-length, I needed to invert the traditional description, as above.

(In fact, I cheated. I used the negative of the metric defined, so I could continue to try to minimise it, and thus use the terms that you and I are familiar with. This complexity didn’t seem worth expounding in the description.)

I wrote in a comment above:

So the question is how do I compare a bad O(n) heuristic against a better O(n*f) heuristic against an unknown quality, unknown complexity heuristic against an O(n!) perfect solution?

Answer: I dunno, but Alastair’s argument of choosing simplicity is a pretty damn strong one. If I was leading a project team doing this for commercial software, I would tell the team to use Jonathon’s solution; it’s both simple and right enough. Luckily, for me, for my private hacking, I get to implement it the hard, fun way!

Confession time!

The proof was in the pudding. I wasn’t happy with my algorithm’s output. I had put in too many tricks to reduce the size of the problem before passing it to the algorithm proper, and the results were noticeably sub-optimal.

If I am going to have a sub-optimal solution, I may as well have a fast sub-optimal solution.

In far less time than it took for one run of my algorithm, I implemented and ran the Jonathon/Aristotle algorithm, and that is the one I am using now.

Thanks guys for your suggestions. I was 0wned again.

FOr some odd reason, this post is still on my mind despite the year having incremented again! Anyhoo, at work I’ve been loosely filling my time read papers on reinforcement learning techniques, and they seem like a good solution for this problem. Specifically, one technique called temporal-difference learning would allow you to learn the best policy for taking an unsorted list and sorting it, using whichever metric you’ve decided on as the “reward”. You’d write some kind of simulator to play a few thousand “episodes” of the problem, and hopefully over time the average metric would increase. You then take whatever weights you’ve now learned for each move, and apply this back to your real iTunes shuffling program.
The only caveat to this is that although you’ll learn a good algorithm in terms of maximising the metric, it may well be very slow. You could alter your metric so that solving the shuffling problem faster was also rewarded, and then you’d be learning a fast and effective algorithm.
At any rate, it’s an interesting way of solving odd problems – I’ve just implemented an AI for a simple snakes game using it! 🙂