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

Question

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

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

Answer 1

Для справки, мой (очень) наивный подход был чем-то вроде этого (на самом деле с использованием вызовов 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 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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