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

The following is the Java program to arrange an array such that no two adjacent numbers are same.

        public int[] rearrangeArray(int[] arr) {
            int n = arr.length;

            // Store frequencies of all elements
            // of the array
            int[] count = new int[1000]; 
            int[] visited = new int[1000]; 

            for (int i = 0; i < n; i++)
                count[arr[i]]++;

            // Insert all characters with their frequencies
            // into a priority_queue
            PriorityQueue<RandomKey> pq = new PriorityQueue<>(11, new KeyComparator());

            // Adding high freq elements in descending order
            for (int i = 0; i < n; i++) {
                int val = arr[i];

                if (count[val] > 0 && visited[val] != 1)
                    pq.add(new RandomKey(count[val], val));
                visited[val] = 1;
            }

            // 'result[]' that will store resultant value
            int[] result = new int[n];

            // work as the previous visited element
            // initial previous element will be ( '-1' and
            // it's frequency will also be '-1' )
            RandomKey prev = new RandomKey(-1, -1);

            // Traverse queue
            int l = 0;
            while (pq.size() != 0) {

                // pop top element from queue and add it
                // to result
                RandomKey k = pq.peek();
                pq.poll();
                result[l] = k.num;

                // If frequency of previous element is less
                // than zero that means it is useless, we
                // need not to push it
                if (prev.freq > 0)
                    pq.add(prev);

                // make current element as the previous
                // decrease frequency by 'one'
                (k.freq)--;
                prev = k;
                l++;
            }

            return result;
        }



     public class RandomKey {

             int freq;
             int num;

            RandomKey(int freq, int num) {
                this.freq = freq;
                this.num = num;
            }
        }


class KeyComparator implements Comparator<RandomKey> {

    // Overriding compare()method of Comparator
    public int compare(RandomKey k1, RandomKey k2) {
        if (k1.freq < k2.freq)
            return 1;
        else if (k1.freq > k2.freq)
            return -1;
        return 0;
    }
}

Answer 2

Here's my algorithm that works for any number of types, not just 2:

• Call a type (e.g. A, B, C, ...) T.
• Call the number of items of type T N(T).

Algorithm in pseudocode:

var size = 0;
for_each (T)
  size += N(T);

var output = array(size); // Initialised to null, to mean gap (no item)
var gapsRemaining = size;

for_each (T)
{
  var itemsRemaining = N(T);
  var i = 0;
  var limit = itemsRemaining / gapsRemaining;
  while (itemsRemaining > 0)
  {
    if (itemsRemaining / (gapsRemaining - i) >= limit)
    { output[{i}th_gap] = next_item_of_type(T)
      gapsRemaining--;
      itemsRemaining--;
    }
    else
      i++;
  }
}

Where the {i}th_gap is zero-based, like the array indexes.

If you can work out {i}th_gap in constant time (which can be done by just using another counter), then the algorithm is linear time, i.e. O(size) O(size * numTypes).

For your example, it gives output a b a b a a b a.

---

Edit

Re-think: it doesn't need to be so complicated if you just maintain counts of each type.

Working JS code (http://js.do/code/96801)

var numItems = [5,3]; // for AAAAABBB
var numItems = [6,3,5]; // for AAAAAABBBCCCCC
var totalNumItems = 0;
for (i=0; i<numItems.length; i++)
    totalNumItems += numItems[i];
var limits = [];
for (i=0; i<numItems.length; i++)
    limits[i] = numItems[i] / totalNumItems;
var numGaps = totalNumItems;
var output = [];
for (i=0; i<totalNumItems; i++)
{   var bestValue = 0;
    var bestType;
    for (j=0; j<numItems.length; j++)
    {   var value = numItems[j] / numGaps - limits[j];
        if (value >= bestValue)
        {   bestValue = value;
            bestType = j;
    }   }
    output[i] = bestType;
    numItems[bestType]--;
    numGaps--;
}
for (i=0; i<totalNumItems; i++)
    document.writeln(output[i]);
document.writeln("<br>");

But as @Jim says, it's O(n * k), where n is totalNumItems and k is numItems.length. So his O(n log k) solution has better complexity.

---

Edit 2

Tweak to break ties better, so more frequent items are preferred. Previous code output for [10,1,1] was caaabaaaaaaa, now is abaaaaacaaaa.

http://js.do/code/96848

var numItems = [10,1,1];
var totalNumItems = 0;
for (i=0; i<numItems.length; i++)
    totalNumItems += numItems[i];
var limits = [];
for (i=0; i<numItems.length; i++)
    limits[i] = numItems[i] / totalNumItems;
var numGaps = totalNumItems;
var output = [];
for (i=0; i<totalNumItems; i++)
{   var bestValue = 0;
    var bestNumItems = 0;
    var bestType;
    for (j=0; j<numItems.length; j++)
    {   var value = numItems[j] / numGaps - limits[j];
        if (value >= bestValue && numItems[j] > bestNumItems)
        {   bestValue = value;
            bestNumItems = numItems[j];
            bestType = j;
    }   }
    output[i] = bestType;
    numItems[bestType]--;
    numGaps--;
}
for (i=0; i<totalNumItems; i++)
    document.writeln(output[i]);
document.writeln("<br>");

Answer 3

Lets say you have A1, A2, ..., An and B1, B2, ..., Bm.

If n>m, then at least 2 A items will be played one after another (if the playlist is cyclic [keeps repeating all]).

You should place the A items on a cycle first. Then place one B item in between every two consecutive A items. This will separate the next-to-next A items. And then place the remaining B items if there is any left.

If you want to make sure that the first and the last items won't be both A, then place an A item at the beginning and place a B item at the end if there are enough B items.

As a computational algorithm, assign numbers (in double type to allow them to be rational numbers) to each A item and order these numbers from smallest to the biggest. Then assign each B item the average of consecutive A items. Ex:

A1=3 A2=5 A3=10

ArrayA(0)=3

ArrayA(1)=5

ArrayA(2)=10

Then let's say you have 4 B items.

 On Error Resume Next

 For n=0 to 3

 ArrayB(n)=(ArrayA(n)+ArrayA(n+1))/2

 Loop

This loop will try to call ArrayA(3) and give an error, we will skip that with on error resume next. You can then assign random numbers to unassigned B items.

At the end, combine two arrays, sort them. You will get sorted numbers. By those numbers, call back the items in an optimally sorted arrangement.

Answer 4

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.

Answer 5

Divide largest array of videos and insert other elements at the point of division.

Video Type A: (An=5)[A1, A2, A3, A4, A5]

Video Type B: (Bn=3)[B1, B2, B3]

 1. Choose the Video type having maximum number of instances, in this
    case A.
 2. Divide: (An=5)[A1, A2, A3, A4, A5] / 2 = 2, (An=2)[A1, A2](An=3)[A3, A4, A5]
 3. Now insert one instance of B at the point of division as per step 1, 
    i.e (An=2)[A1, A2](Bn=1)[B1](An=3)(A3, A4, A5)
 4. Now repeat step 2, 3 with (An=2)[A1, A2]  and   (An=3)[A3, A4, A5] and so forth like we do in binary search.
    Final arrangement: (An=1)[A1](Bn=1)[B2](An=1)[A2](Bn=1)[B1](An=2)[A3, A4](Bn=1)[B3](An=1)[A5]

Answer 6

The question doesn't seem so easy as the number of combinations is large. If I am right, for Na, Nb and Nc videos of three types, there are (Na+Nb+Nc-1)!/Na!Nb!Nc! possibilities. (The -1 in the numerator coming from the fact that sequences that are a cyclic permutation of each other are considered identical.)

Not having a clear understanding of the combinatorial structure, I would try as follows:

• define a merit figure that rates how well a playlist is dispersed. That could be the sum of (cyclic) distances between videos from the same set.

For example

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

gives

2+2+2+2+2+4+1+1 = 16

and

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

gives

2+3+1+2+2+2+3+1 = 16

(this is probably an unsufficient metric, short distance should be more penalized.)

• try random sequences by choosing among the available types until they are exhausted, and rate the sequences. After a number of random trials, keep the best score. [I would simulate drawing without replacement so that the different types are consumed in a balanced way.]

For small N, exhaustive trials are possible.

Update:

Suprizingly, the simple metric that I suggested gives a constant value !