Shuffle a list (with duplicates) to avoid identical elements being next to each other

Question

Hi,

I am wondering if there is a "best" way to shuffle a list of elements that contains duplicates such that the case where array[i] == array[i+1] is avoided as much as possible.

I am working on a weighted advertising display (I can adjust the number of displays per rotation for any given advertiser) and would like to avoid the same advertister appearing twice in a row.

Answer 1

What's the biggest number of duplicates you may have? 2, 3, any?

Answer 2

Personally I think the easiest way to hand this would be to randomize the array, and then iterate over it until you find 2 elements with the same value that are next to each other. When you find 2 of the same values beside eachother, move the later one to another spot in the array by iterating over the array until you find a spot such that it isn't beside another of the same value. If you can't find a value, just leave it where it is, and continue on with the next element of the array. This probably won't be the most optimal solution, but will be fine for smaller data sets, and probably the simplest to program.

Answer 3

This is pretty similar to this question. If you replace A, B, and C in the example given over there with your advertisers, I think you arrive at the same problem. Maybe some of the solutions suggested for that one can help you.

Answer 4

For reference, my (very) naive approach was something like this (actually using LINQ/SQL calls but this is simplified):

var advertisers = getAdvertisers();
var returnList = new List();
int totalWeight = sumOfAllAdvertisersWeight();
while (totalWeight > 0)
{
    for (int i=0; i<advertisers.Count; i++)
    {
        if (advertisers[i].Weight > 0)
        {
            returnList.add(advertisers[i]);
            advertisers[i].Weight--;
            totalWeight--;
        }
    }
}
return returnList;

This will avoid duplicates until the end but yeah it would pay to check backwards through the returnList afterwards and if there are any duplicates tailing, try and place them in the mix earlier.