¿cuál es la forma más eficiente para recoger una carta al azar de una baraja cuando algunas tarjetas no se pueden utilizar?

StackOverflow https://stackoverflow.com/questions/1133942

Pregunta

Tengo una matriz que indica si una tarjeta está en uso: 

int used[52];

Esta es una forma terrible para recoger una carta al azar si tengo muchas cartas usadas: 

do {
  card = rand() % 52;
} while (used[card]);

ya que si tengo sólo 3-4 tarjetas no utilizadas, que va a tener para siempre para encontrarlos.

Se me ocurrió esto: 

 int card;
 int k = 0;
 int numUsed = 0;
 for (k=0; k < 52; ++k) {
   if (used[k]) numUsed += 1;
 }
 if (numUsed == 52) return -1;
 card = rand() % (52 - numUsed);

 for (k=0; k < 52; ++k) {
   if (used[k]) continue;
   if (card == 0) return k;
   card -= 1;
 }

que supongo que funciona mejor si la cubierta está llena, pero funciona peor cuando la cubierta está vacío ya que tengo que pasar por dos bucles.

¿Cuál es la forma más eficiente de hacer esto?

¿Fue útil?

Solución

Creo que su algoritmo de dos pasos es probable que sea lo mejor que puede hacer, dada la limitación agregó en un comentario que no se sabe de antemano que las tarjetas son elegibles para un sorteo determinado.

Usted podría intentar la astucia "seleccionar al azar de una lista de tamaño desconocido en una sola pasada" algoritmo: 

int sofar = 0;
int selected = -1;
for (i = 0; i < 52; ++i) {
    if (used[i]) continue;
    ++sofar;
    if ((rand() % sofar) == 0) selected = i;
}
if (selected == -1) panic; // there were no usable cards 
else used[selected] = 1;   // we have selected a card

A continuación, si (como se dice en un comentario) dibuja diferentes tienen diferentes criterios, puede reemplazar used[i] con lo que los criterios son reales.

La forma en que funciona es que se selecciona la primera tarjeta. A continuación, se sustituya por la segunda tarjeta con probabilidad 1/2. Reemplazar el resultado con la tercera tarjeta con probabilidad 1/3, etc. Es fácil demostrar por inducción que después de n pasos, la probabilidad de cada uno de los tarjetas anteriores, que es la seleccionada, es 1 / n.

Este método utiliza una gran cantidad de números aleatorios, por lo que es probable que sea más lento que la versión de dos pasadas a menos conseguir cada artículo es lento, o la evaluación de los criterios es lento. Normalmente se había utilizarse por ejemplo para seleccionar al azar una línea de un archivo, en el que realmente no desea ejecutar sobre los datos dos veces. También es sensible a sesgo en los números aleatorios.

Es bueno y sencillo, sin embargo.

[Editar: prueba

Sea p (j, k) la probabilidad de que el número de tarjeta j es la tarjeta actualmente seleccionado después de la etapa k.

requeridos para probar: para todo n, p (j, n) = 1 / n para todos 1 <= j <= n

Para n = 1, obviamente p (1,1) = 1, ya que la primera tarjeta se selecciona en el primer paso con una probabilidad de 1/1 = 1.

Supongamos que p (j, k) = 1 / k para todos 1 <= j <= k.

A continuación, seleccionamos el (k + 1) -ésimo tarjeta en el paso (k + 1) con una probabilidad de 1 / (k + 1), es decir p (k + 1, k + 1) = 1 / (k + 1) .

Nos reservamos la selección existente con probabilidad k / (k + 1), así que para cualquier j 

p(j,k+1) = p(j,k) * k/(k+1)
         = 1/k    * k/(k+1)   // by the inductive hypothesis
         = 1/(k+1)

Así p (j, k + 1) = 1 / (k + 1) para todos 1 <= k <= k + 1

Por lo tanto, por inducción, para todo n: p (j, n) = 1 / n para todos 1 <= j <= n]

Otros consejos

¿Por qué no te quedas con otra colección de tarjetas no utilizadas?

Si usted los quiere en orden aleatorio, se puede mezclar primero de ellos ( Fisher-Yates ), entonces pop a retirarse a medida que los necesite.

La mejor manera de hacerlo es a barajar las cartas en un orden aleatorio, y luego recoger la primera tarjeta sin usar. Esta es la forma más común para realizar una reproducción aleatoria de esta manera.

El algoritmo estándar para repartir las cartas al azar es.

  • inicializar la cubierta para contener todas las tarjetas (orden no es importante)
  • bucle:
  • generar índice aleatorio en el rango 0 a la cubierta de tamaño - 1
  • tarjeta de visualización en ese índice (o hacer lo que quiera)
  • tarjeta de intercambio indexadas en la cubierta con la tarjeta en [cubierta de tamaño -1]
  • reducir la cubierta de tamaño por uno
  • goto bucle: tan a menudo como se requiere

Se podría deshacerse de los dos bucles utilizando un código como: 

int card;
int k = 0;
int i = 0;
int unUsed[52];
int numUsed = 0;
for (k = 0; k < 52; ++k) {
  if (used[k]) {
    numUsed += 1;
  } else {
    unUsed[i] = k;
    i++;
  }
}
if (numUsed == 52) return -1;
card = rand() % (52 - numUsed);
return unUsed[card];

A pesar de que se imagina el aumento de la eficiencia no sería grande, y que va a utilizar más memoria.

La otra opción sería tener dos listas, utilizar uno para realizar un seguimiento de las tarjetas utilizadas y uno para rastrear las tarjetas no utilizadas. Así que si se utiliza una tarjeta, restarlo de listas de tarjetas no utilizadas y añadirlo al final de la lista de la tarjeta utilizada. De esta manera, usted no tendrá que ejecutar dos bucles cada vez.

Mantenga las tarjetas usadas en el final de la matriz y las tarjetas no utilizadas en el principio. Mantenga un registro de cuántas cartas no se han utilizado todavía. Cuando se utiliza una tarjeta nueva, intercambiar con la última carta sin usar y disminuir el número de cartas restantes. 

if (numRemaining == 0) return -1;
int cardNum = rand() % numRemaining;
Card card = cards[cardNum]; // or int, if cards are represented by their numbers
cards[cardNum] = cards[numRemaining - 1];
cards[numRemaining - 1] = card;
numRemaining--;

No estoy seguro de si esto va a producir realmente al azar dibuja, pero sería evitar bucles a través de toda la cubierta en casi todos los casos. Estoy aún menos seguro de lo que sería aconsejable comparar el rendimiento, pero aquí no es menos:

  • obtener carta al azar de mazo
  • si la tarjeta ya se utiliza, recoger una dirección aleatoria (hacia adelante o hacia atrás)
  • paso Trough la cubierta desde la posición actual en el sentido determinado al azar hasta encontrar la siguiente carta sin usar (por supuesto, usted tiene que asegurarse de que está adecuadamente envolver alrededor de los extremos de la matriz)

Así que en el peor de los casos, elegir una tarjeta justo al lado de la anterior sin usar y luego paso a través de la cubierta en la dirección 'equivocada', realizando así un bucle completo a través de la cubierta.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top