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

Question

Мне интересно, есть ли «лучший» способ перетасовать список элементов, содержащих дубликаты, так что случай, когда array [i] == массив [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

Самое большое количество дубликатов, которые у вас могут быть? 2, 3, любой?

Answer 3

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

Answer 4

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

Answer 5

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

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

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