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

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

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

11.12.2008 02:43:14
5 ОТВЕТОВ

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

0
11.12.2008 02:52:57
Ну, из-за веса, например, рекламодатель 1 может появляться 5 раз за оборот, легко может быть 5 дубликатов.
Matt Mitchell 11.12.2008 02:57:50

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

1
11.12.2008 02:53:13
хм, может быть все в порядке, но это что до O (n ^ 2)?
Matt Mitchell 11.12.2008 02:57:20
Вероятно, о O (n ^ 2), но средний случай, вероятно, будет намного ниже, если вы не ожидаете много дубликатов.
Kibbee 11.12.2008 03:00:33
Да, и алгоритм, по крайней мере, прост - всегда можно оптимизировать позже. Хотелось бы, чтобы они учили нас решать проблемы в университете.
Matt Mitchell 11.12.2008 03:01:20
Самым худшим случаем будет O (n ^ 2), но я не ожидаю, что вы попадете туда со случайным перемешиванием. Ваш средний случай будет близок к O (n).
Bill the Lizard 11.12.2008 03:02:31
У Джеффа есть хорошая статья
Bill the Lizard 11.12.2008 03:03:37

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

2
23.05.2017 11:45:25

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

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

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

Генератор случайных чисел Дилберта

2
8.02.2017 14:08:14
РЕШЕНИЕ

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

0
11.12.2008 09:58:53
В условном условии есть опечатка.
Svante 11.12.2008 03:52:26