Add random class from an array to every specified element, excluding last used class

I have an array with classes and i want to apply random class from this array to specified elements - this is simple. But i need to avoid situation like two or more elements in a row has the same class.

For now i have something like this:

$(document).ready(function(){
    var classes = ["bg1", "bg2", "bg3", "bg4", "bg5"];

    $(".img-cap").each(function(){
        $(this).addClass(classes[~~(Math.random()*classes.length)]);
    });
});