Efficient algorithm for ordering different types of objects

Question

Given that we have a collection of videos of different types (say types A,B and C,...), we are looking for an efficient algorithm to order these objects into a playlist so that we have maximum dispersion. That is, we want to make sure that two videos from A will not be placed back to back, if that can be avoided. The playlist will be repeating (it starts over when it ends. So this aspect should also be considered).

What would be an efficient algorithm that could perform the above with a good dispersion?

Example Input:

• 5 objects of type A (A1, A2, A3, A4, A5)
• 3 objects of type B (B1, B2, B3)

Output - Not Optimal

A1, B1, A2, B2, A3, B3, A4, A5

This is not optimal because after A4, A5 plays and then the playlist loops back and A1 plays. Now we have played 3 videos from type A back to back.

An Optimal Output

A1, B1, A2, A3, B2, A4, B4, A5

This is optimal because we have only 2 videos of same type playing back to back.

Note that the algorithm should work for varying number of types and videos.

Answer 1

This is similar to a problem I encountered a couple of years ago: mixing liquids to avoid stratification. The idea is that if you're mixing liquids A, B, and C into a container, you don't want to just pour them into the container one after the other. Rather, you want to add some A, some B, some C, etc., in the relative proportions.

It's the same problem as evenly distributing items in a list.

Say you have 30 of type A, 20 of type B, and 10 of type C, for a total of 60 videos. Every other video, then, has to be an A. Every third video is a B, and every sixth video is a C.

So the A's are at 0,2,4,6,8,etc. B's are at 0,3,6,9,12,etc. And the C's are at 0,6,12,18,etc.

Obviously, you have collisions that you must resolve.

The way I did this is to build a min heap that contains the video type and its frequency, and its current position, which starts at frequency/2. So the heap contains: {A,2,1},{B,3,1},{C,6,3}.

To generate your list, remove the lowest item from the heap and add it to your list. Then, add its frequency to the current position, and put it back on the heap. So after the first time through, you've output the A, and your heap now contains: {B,3,1},{A,2,2},{C,6,3}.

Output the B, and then add it back, giving you {A,2,2},{C,6,3},{B,3,4}

You'll of course also want to keep a count of each item, which you decrement each time that item is output, and you don't add it back to the heap if the count goes to 0.

I wrote about this at some length in my blog about a year ago. See Evenly distributing items in a list.

As far as efficiency is concerned, the algorithm has complexity O(n log k), where n is the total number of videos, and k is the number of video types.