ce qui est la façon la plus efficace de choisir une carte au hasard à partir d'une plate-forme lorsque certaines cartes sont inutilisables?

Question

J'ai un tableau qui indique si une carte est en cours d'utilisation:

int used[52];

Ceci est une façon terrible de choisir une carte au hasard si j'ai beaucoup de cartes utilisées:

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

car si je n'ai que 3-4 cartes inutilisées, ça va prendre une éternité pour les trouver.

Je suis venu avec ceci:

 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 je suppose fonctionne mieux si le pont est plein, mais fonctionne pire lorsque le pont est vide depuis que je dois passer par deux pour les boucles.

Quelle est la façon la plus efficace de le faire?

Answer 1

Je pense que votre algorithme en deux passes est susceptible d'être le meilleur que vous pouvez faire, étant donné la contrainte que vous avez ajouté dans un commentaire que vous ne savez pas à l'avance quelles cartes sont admissibles à un tirage donné.

Vous pouvez essayer la ruse « choisir au hasard dans une liste de taille inconnue en un seul passage » algorithme:

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

Alors, si (comme vous le dites dans un commentaire) différents tirages ont différents critères, vous pouvez remplacer used[i] avec quelles que soient les critères réels.

La façon dont cela fonctionne est que vous sélectionnez la première carte. Ensuite, vous le remplacez par la deuxième carte avec une probabilité 1/2. Remplacer le résultat avec la troisième carte avec une probabilité 1/3, etc. Il est facile de prouver par induction qu'après n étapes, la probabilité de chacune des cartes précédentes étant celle sélectionnée, est 1 / n.

Cette méthode utilise beaucoup de nombres aléatoires, il est donc probablement plus lent que votre version à deux passes à moins d'obtenir chaque élément est lent ou l'évaluation des critères est lent. Il serait normalement utilisé par exemple pour sélectionner une ligne au hasard dans un fichier, où vous ne voulez vraiment pas courir sur les données deux fois. Il est également sensible aux biais dans les nombres aléatoires.

Il est bon et simple, cependant.

[Edit: la preuve

Soit p (j, k) est la probabilité que le numéro de carte j est la carte actuellement sélectionné après l'étape k.

Obligation de prouver: pour tout n, p (j, n) = 1 / n pour tout 1 <= j <= n

Pour n = 1, p évidemment (1,1) = 1, étant donné que la première carte est sélectionnée lors de la première étape avec une probabilité de 1/1 = 1.

Supposons que P (j, k) = 1 / k pour tout 1 <= j <= k.

Ensuite, nous choisissons la (k + 1) ième carte à l'étape (k + 1) avec une probabilité 1 / (k + 1), soit p (k + 1, k + 1) = 1 / (k + 1) .

Nous maintenons la sélection existante avec une probabilité de k / (k + 1), de sorte que pour tout j

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

p (j, k + 1) = 1 / (k + 1) pour tout 1 <= k <= k + 1

Ainsi, par induction, pour tout n: p (j, n) = 1 / n pour tout 1 <= j <= n]

Answer 2

Pourquoi ne pas garder juste une autre collection de cartes inutilisées?

Si vous voulez dans un ordre aléatoire, vous pouvez d'abord les mélanger ( Fisher-Yates ), puis les pop off que vous avez besoin.

Answer 3

La meilleure façon de le faire est de mélanger la plate-forme dans un ordre aléatoire, puis choisissez la première carte inutilisée. Voici la façon la plus courante pour effectuer une lecture aléatoire comme celui-ci.

Answer 4

L'algorithme standard pour le traitement des cartes aléatoires est.

• initialiser la plate-forme pour contenir toutes les cartes (ordre n'a pas d'importance)
• boucle:
• générer indice aléatoire dans la plage allant de 0 à la taille de plate-forme - 1
• carte d'affichage à l'index (ou faire ce que vous voulez)
• carte indexé swap sur le pont avec la carte à [taille du pont -1]
• réduire la taille de plate-forme par un
• boucle goto: aussi souvent que nécessaire

Answer 5

Vous pouvez vous débarrasser des deux boucles en utilisant un code comme:

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

Bien que j'imagine l'augmentation de l'efficacité ne serait pas grand, et que vous allez utiliser plus de mémoire.

Answer 6

L'autre option serait d'avoir deux listes, utilisez l'une pour suivre les cartes utilisées et l'autre pour suivre les cartes inutilisées. Donc, si vous utilisez une carte, soustraire des listes de cartes inutilisées et l'ajouter à la fin de la liste des cartes utilisées. De cette façon, vous ne serez pas à courir deux pour les boucles à chaque fois.

Answer 7

Gardez les cartes utilisées à la fin du tableau et les cartes inutilisées au début. Gardez une trace de combien de cartes ont pas été encore utilisé. Lorsqu'une nouvelle carte est utilisée, échanger avec la dernière carte inutilisée et décrémenter le nombre de cartes 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--;

Answer 8

Knuth aléatoire dans de nombreuses langues

Answer 9

Je ne suis pas sûr que cela produira vraiment des tirages au sort, mais il serait d'éviter les boucles à travers la plate-forme entière dans presque tous les cas. Je suis encore moins sûr de savoir comment il serait sage de comparer les performances, mais ici, il est tout de même:

• obtenir une carte aléatoire de plate-forme
• si la carte est déjà utilisé, choisissez une direction aléatoire (vers l'avant ou vers l'arrière)
• pas cuvette la plate-forme de la position actuelle dans le jusqu'à ce que vous trouver une direction au hasard déterminé la prochaine carte utilisé (bien sûr, vous devez vous assurer que vous êtes correctement enroulant autour aux extrémités du tableau)

Ainsi, dans le pire des cas, vous choisissez une carte juste à côté de la dernière étape, puis utilisé par la plate-forme dans le sens « mauvais », réalisant ainsi une boucle complète à travers le pont.