Mescola un elenco (con duplicati) per evitare che elementi identici siano uno accanto all'altro

Question

Mi chiedo se esista un modo "migliore" per mescolare un elenco di elementi che contiene duplicati in modo tale da evitare il più possibile il caso in cui array[i] == array[i+1].

Sto lavorando su una visualizzazione pubblicitaria ponderata (posso modificare il numero di visualizzazioni per rotazione per ogni inserzionista) e vorrei evitare che lo stesso inserzionista appaia due volte di seguito.

Answer 1

Per riferimento, il mio (molto) approccio ingenuo è stato qualcosa di simile (in realtà utilizzando le chiamate / SQL LINQ, ma questo è semplificata):

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;

Questo permetterà di evitare i duplicati fino alla fine ma sì che avrebbe pagato per controllare a ritroso attraverso il returnList in seguito e se ci sono dei duplicati tailing, cercare di metterli nel mix precedente.

Answer 2

Questo è abbastanza simile a questa domanda . Se si sostituisce A, B, e C nell'esempio dato laggiù con i tuoi inserzionisti, credo che si arriva allo stesso problema. Forse alcune delle soluzioni proposte per questo si può fare a voi.

Answer 3

La randomizzazione di base dovrebbe causare una dispersione sufficiente in un insieme ampio.

Se vuoi minimizzarlo ancora di più (il che potrebbe non essere nemmeno necessario a seconda dei set), il modo più semplice sarebbe trovare sicuramente i duplicati vicini dopo la randomizzazione e spostarli (ma potresti creare modelli).Un approccio migliore potrebbe essere quello di creare sottoinsiemi contenenti i duplicati affiancati e ripetere la randomizzazione.

Per un set più piccolo potrebbe non essere possibile nulla, a seconda del numero di duplicati.Quindi la soluzione per un insieme molto piccolo sarebbe solo una buona randomizzazione di base (e torniamo alla prima frase).

Answer 4

Personalmente penso che il modo più semplice a portata di mano questo sarebbe quello di randomizzare l'array, e poi scorrere su di esso fino a trovare 2 elementi con lo stesso valore che sono uno accanto all'altro. Quando si trova 2 degli stessi valori accanto a vicenda, spostare quella successiva in un altro punto nella matrice dalla iterazione di matrice fino a trovare un punto tale che non è accanto un altro dello stesso valore. Se non è possibile trovare un valore, basta lasciarlo dove si trova, e continuare con il prossimo elemento della matrice. Questo probabilmente non sarà la soluzione più ottimale, ma andrà bene per i set di dati più piccoli, e probabilmente il più semplice da programmare.

Answer 5

Qual è il più grande numero di duplicati si possono avere? 2, 3, qualsiasi?