Перемешать список (с дубликатами), чтобы идентичные элементы не были рядом друг с другом

Question

Мне интересно, есть ли «лучший» способ перемешать список элементов, который содержит дубликаты, так, чтобы максимально избежать случая, когда array [i] == array [i + 1].

Я работаю над взвешенным показом рекламы (я могу настроить количество показов за оборот для любого рекламодателя) и хотел бы, чтобы один и тот же рекламодатель не появлялся дважды подряд.

Answer 1

Базовая рандомизация должна вызывать достаточную дисперсию в большом наборе.

Если вы хотите минимизировать это еще больше (что может даже не потребоваться в зависимости от наборов), самый простой способ будет определенно находить близких по дупсам после рандомизации и перемещать их вокруг (но вы можете создавать шаблоны). Лучшим подходом может быть создание подмножеств, содержащих бок о бок дупы и повторное рандомизирование.

Для меньшего набора ничего не может быть возможно, в зависимости от количества дупликов. Таким образом, решением для очень маленького набора будет хорошая базовая рандомизация (и мы вернулись к первому предложению).

Answer 2

Это очень похоже на этот вопрос . Если вы замените A, B и C в приведенном там примере своими рекламодателями, я думаю, что вы столкнетесь с той же проблемой. Может быть, некоторые из предложенных решений помогут вам.

Answer 3

Лично я думаю, что самый простой способ передать это - это рандомизировать массив, а затем перебирать его, пока не найдете 2 элемента с одинаковым значением, которые находятся рядом друг с другом. Когда вы найдете 2 одинаковых значения рядом друг с другом, переместите последнее в другое место в массиве, перебирая массив, пока не найдете такое место, что оно не будет рядом с другим тем же значением. Если вы не можете найти значение, просто оставьте его там, где оно есть, и переходите к следующему элементу массива. Это, вероятно, не самое оптимальное решение, но оно подойдет для небольших наборов данных и, возможно, является самым простым для программирования.

Answer 4

Для справки, мой (очень) наивный подход был примерно таким (фактически с использованием вызовов LINQ / SQL, но это упрощено):

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;

Это позволит избежать дубликатов до конца, но да, это будет стоить проверять обратный просмотр через returnList впоследствии, и если есть какие-либо дубликаты, попробуйте и поместите их в микс раньше.

Answer 5

Какое наибольшее количество дубликатов у вас может быть? 2, 3, любой?