Перемешайте список (с дубликатами), чтобы идентичные элементы не находились рядом друг с другом
-
21-08-2019 - |
Вопрос
Мне интересно, есть ли "лучший" способ перетасовать список элементов, содержащий дубликаты, таким образом, чтобы максимально избежать случая, когда array[i] == array[i+ 1].
Я работаю над взвешенным показом рекламы (я могу регулировать количество показов за ротацию для любого данного рекламодателя) и хотел бы избежать появления одного и того же рекламодателя дважды подряд.
Решение 5
Для справки, мой (очень) наивный подход был чем-то вроде этого (на самом деле с использованием вызовов 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 впоследствии, и если есть какие-либо дубликаты, попробуйте поместить их в микс раньше.
Другие советы
Это очень похоже на этот вопрос.Если вы замените A, B и C в приведенном выше примере на своих рекламодателей, я думаю, вы столкнетесь с той же проблемой.Возможно, некоторые из предложенных для этого решений помогут вам.
Базовая рандомизация должна привести к достаточной дисперсии в большом наборе.
Если вы хотите свести это к минимуму еще больше (что может даже не понадобиться в зависимости от наборов), самым простым способом было бы определенно найти близкие дубликаты после рандомизации и переместить их (но вы можете создавать шаблоны).Лучшим подходом могло бы быть создание подмножеств, содержащих параллельные дубликаты, и повторение рандомизации.
Для меньшего набора ничего не может быть возможным, в зависимости от количества дубликатов.Таким образом, решением для очень небольшого набора была бы только хорошая базовая рандомизация (И мы возвращаемся к первому предложению).
Лично я думаю, что самым простым способом передать это было бы рандомизировать массив, а затем выполнять итерации по нему, пока не найдете 2 элемента с одинаковым значением, которые находятся рядом друг с другом.Когда вы найдете 2 одинаковых значения рядом друг с другом, переместите более позднее значение в другое место в массиве, выполняя итерации по массиву, пока не найдете место, отличное от другого с тем же значением.Если вы не можете найти значение, просто оставьте его там, где оно есть, и переходите к следующему элементу массива.Вероятно, это не самое оптимальное решение, но оно подойдет для небольших наборов данных и, вероятно, самое простое в программировании.
Какое наибольшее количество дубликатов у вас может быть?2, 3, какие-нибудь?