If you’re building a music log for a radio station, you generally have certain rules determined by your format — for example:

• All of the top 10 songs get played once every jock shift
• All of the next 20 songs get played at least three times a day, including once in both drive-time dayparts
• No song gets played during the same hour on consecutive weekdays
• No artist gets played twice within two hours, except as part of a special promotion
• No “train-wreck” segues

In the old days (the “golden age of top-40 radio”), the music log was developed iteratively by the jocks using a set of index cards in file boxes: they’d take a card from box A, play the song shown on the card, make a note on the card to say when it was last played, and then put it back in the box to await its next turn in the rotation. Next song comes from box B, and so on. To add a song to the playlist, the music director would make up a new card and add it to the appropriate box — and songs would get moved from box to box depending on what their current role in the format was.

These days, humans are expensive, so you’d like the log to be generated automatically, fit within your format’s clock, and have exactly enough room for the commercial inventory your salespeople are able to sell, without requiring jocks to do any thinking, or even to be present in the studio. (There are commercial programs, notably Selector, which actually do this, and feed into automation systems.)

To put it in more formal terms: you have a set P (the playlist) consisting of tuples designating songs and format-relevant properties of those songs, one of those properties being the length of the song. The set L is the set of all music logs l, each l being an ordered list of elements of P whose lengths sum to within ε of some maximum history interval t (t being much larger than the length of any individual song). There is a constraint set C of predicates on L, which defines L′ ⊆ L permissible music logs, i.e., those elements of L for which all C are true. Assume for the sake of argument that you could precompute L′ (which is obviously impractical) and that it is nontrivial (i.e., there exists more than one l which satisfies all of C).

So here’s the algorithms question: is there an on-line procedure to generate feasible logs which is indistinguishable from a uniform random selection from L′? By on-line I mean one that models each log as a finite stream of elements from P, without lookahead (or with lookahead limited to t′ ≪ t). Assume that all of the constraints can be formulated to apply identically to prospective and retrospective playlists. If it is not possible, how close can you come?

(I don’t know the answer. I tried to ask Charles Leiserson once, but there was something of a language barrier on my part. You could obviously imagine applying a similar technique for personal music-player playlists, which is actually the context in which I originally thought of this. Scott and I talked once, several years ago, about trying to convince RCS to make a consumer version of Selector — something you could point at a music library and say things like “make me a playlist that sounds like what Sunny Joe White would have done at Kiss 108 in 1985”, or even just entering your own music-radio-style adjacency rules. But the business model probably isn’t there, so it remained a fantasy.)