Come randomizzare un elenco ordinato?

Question

Ecco una strana domanda per voi ragazzi,

Ho una bella lista ordinata che desidero randomizzare. Come potrei fare per farlo?

Nella mia applicazione, ho una funzione che restituisce un elenco di punti che descrivono il contorno di un oggetto discretizzato. A causa del modo in cui il problema viene risolto, la funzione restituisce una bella lista ordinata. Ho un secondo limite descritto in matematica e voglio determinare se i due oggetti si intersecano tra loro. Semplicemente eseguo l'iterazione sui punti e determina se un punto è all'interno del limite matematico.

Il metodo funziona bene ma voglio aumentare la velocità randomizzando i dati del punto. Dal momento che è probabile che il mio limite matematico sarà sovrapposto a una serie di punti che sono proprio uno accanto all'altro, penso che avrebbe senso controllare una lista randomizzata piuttosto che scorrere su una bella lista ordinata (poiché richiede solo un singolo colpire per dichiarare un'intersezione).

Quindi, qualche idea su come andrei sul randomizzare una lista ordinata?

Answer 1

Utilizzare std::random_shuffle. Se vuoi implementare il metodo da solo, dovresti guardare lo Fisher-Yates shuffle.

Answer 2

È possibile provare lo random_shuffle algorithm, ma si noti che non funzionerà su list poiché richiede iteratori di accesso casuale. Puoi usarlo su un vector o deque, però.

Answer 3

std::random_shuffle(thelist.begin(), thelist.end()); 

Answer 4

Assumendo che il "lista" non significa una lista collegata, ma invece significa qualcosa che supporta l'accesso casuale (ad esempio, un array, std :: vector, o std :: deque), std :: random_shuffle potrebbe essere utile

Answer 5

Ma una domanda chiave sarebbe se il runtime richiesto per randomizzare l'elenco potrebbe non essere superiore al tempo di esecuzione per attraversarlo in sequenza.

Forse ciò che realmente devi fare non è in realtà casuale, ma piuttosto leggerlo in un ordine diverso dal fronte al retro. Ad esempio, se la lista ha n membri, forse dovresti elaborare 1, n, 2, n-1, 3, n-2, ecc. O 1, n/2, 2, n/2 + 1, 3, n/2 +2, ecc.

Se si ottiene sempre lo stesso numero di punti o se il numero di punti rientra in un piccolo insieme finito, è possibile produrre una valutazione del punteggio per ogni possibile numero di punti una volta in anticipo , o veramente casuale o forse accuratamente calcolato in qualche modo.

Answer 6

 
int array[N]; 

for(int i = N - 1; i > 0; i--) { 
    int j = rand() % i; 
    int tmp = array[i]; array[i] = array[j]; array[j] = i; 
}