¿Cómo aleatorizar una lista ordenada?

Question

Aquí hay una pregunta extraña para ustedes,

Tengo una buena lista ordenada que deseo aleatorizar. ¿Cómo voy a hacer eso?

En mi aplicación, tengo una función que devuelve una lista de puntos que describen el contorno de un objeto discretizado. Debido a la forma en que se resuelve el problema, la función devuelve una lista ordenada. tengo un segundo límite descrito en matemáticas y quiero determinar si los dos objetos se cruzan entre sí. Simplemente analizo los puntos y determino si algún punto está dentro del límite matemático.

El método funciona bien, pero quiero aumentar la velocidad aleatorizando los datos del punto. Dado que es probable que mi límite matemático se solape con una serie de puntos que están uno junto al otro, creo que tendría sentido verificar una lista aleatorizada en lugar de iterar sobre una buena ordenada (ya que solo se necesita una sola golpear para declarar una intersección).

¿Alguna idea sobre cómo haré para aleatorizar una lista ordenada?

Answer 1

Utilice std::random_shuffle. Si desea implementar el método usted mismo, debe mirar el Fisher-Yates shuffle.

Answer 2

Puede probar el random_shuffle algorithm, pero tenga en cuenta que no funcionará en list ya que requiere iteradores de acceso aleatorio. Sin embargo, puede usarlo en vector o deque.

Answer 3

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

Answer 4

Asumiendo que su "lista" no significa una lista enlazada, pero en vez significa algo que admite el acceso aleatorio (por ejemplo, una matriz, std :: vector, o std :: deque), std :: random_shuffle podría ser útil.

Answer 5

Pero una pregunta clave sería si el tiempo de ejecución requerido para aleatorizar la lista podría no ser más que el tiempo de ejecución para recorrerlo secuencialmente.

Quizás lo que realmente necesita hacer no es aleatorizarlo, sino leerlo en un orden que no sea de adelante hacia atrás. Por ejemplo, si la lista tiene n miembros, quizás deba procesar 1, n, 2, n-1, 3, n-2, etc. o 1, n/2, 2, n/2 + 1, 3, n/2 +2, etc.

Si siempre tiene el mismo número de puntos o si el número de puntos cae en un pequeño conjunto finito, puede producir una orden de evaluación de puntos para cada posible número de puntos una vez por adelantado , ya sea verdaderamente al azar o tal vez cuidadosamente calculado de alguna manera.

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; 
}