How to rearrange data in array so that two similar items are not next to each other?

After I grasped what you're after, here's a possible solution

1. Partition your array

   [1,1,1,8,8,8,2,3,3,4,1,1,1,2,2] -> [[3,1],[3,8],[1,2],[2,3],[1,4],[3,1],[2,2]]
   

   (read 3 times 1, 3 times 8, and so on)

2. For each partition entry i with p[i][0] >1 (times >1):

   • Choose a "valid" position j (so p[j][1] != p[i][1] && p[j+1][1] != p[i][1])

   • Decrement p[i][0] element and insert [p[i][1],1] in partition at position j

   or leave it out if there is no such position.

This should have linear time complexity (book-keep valid positions for each number).

Take the entire array and scan it for duplicates. When you encounter dupes, remember where they are. So for something like 2 1 2 2* 3 3* 3* 4 4* 2 2* 5. The ones with stars should be remembered.

Now look at the "Remembered" stuff, you have 2 2's, 2 3's and a 4

Now I'd sort those LISTS the most numerous first (2's and 3's) to the least numerous (4's)

Now just take the most numerous that doesn't duplicate the current "Front" (which would be 3 because 2 duplicates) and move it to the front, then remove it from your list.

repeat until the lists are empty. The second time through your list will start with "3" and you will have 2 2's a 3 and a 4, so you'll put one of the 2's in the front...

If you have any left (it can only be one number) put it at the end..

done, cake.

In javascript, I'd probably do:

    var arr = [ 1, 1, 1, 2, 3 ];
    var i = 0, len = arr.length;

    while (i < len - 1) {
        if (arr[i] == arr[i+1]) {
            //index is equal to it's partner.
            if (arr[i+2] && arr[i] == arr[i+2]) {
                // 3 equal values in a row, swapping won't help. Need to recheck this index in this case.
                var tmp = arr[i];
                arr.splice( i, 1 );
                arr.push( tmp );
            } else {
                // Swap the next and 2nd next index.
                var tmp = arr[i+1];
                arr[i+1] = arr[i+2];
                arr[i+2] = tmp;
                i++;
            }
        } else {
            // this index is fine, move on.
            i++;
        }
    }

This is a quick example, coding style could probably be cleaned up a lot