o que é a forma mais eficiente para escolher uma carta aleatória de um baralho quando alguns cartões não são utilizáveis?

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

Pergunta

Eu tenho uma matriz que diz se um cartão está em uso: 

int used[52];

Esta é uma péssima maneira de escolher um cartão aleatório se eu tiver muitos cartões usados: 

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

desde se eu tiver apenas 3-4 cartões não utilizados, vai demorar uma eternidade para encontrá-los.

Eu vim com isso: 

 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 eu acho que funciona melhor se o pavimento está cheio, mas funciona pior quando o pavimento está vazio desde que eu tenho que passar por dois para loops.

O que é a maneira mais eficiente de fazer isso?

Foi útil?

Solução

Eu acho que seu algoritmo de duas passagens é susceptível de ser o melhor que você pode fazer, dada a restrição você adicionou em um comentário que você não sabe com antecedência quais cartões são elegíveis para um determinado sorteio.

Você poderia tentar a astúcia "seleccionar aleatoriamente de uma lista de tamanho desconhecido em uma única passagem" 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

Então, se (como você diz em um comentário) diferente desenha têm critérios diferentes, você pode substituir used[i] com o que os critérios atuais são.

O modo como funciona é que você selecionar o primeiro cartão. Então você substituí-lo com o segundo cartão com probabilidade 1/2. Substituir o resultado com o terceiro cartão com probabilidade 1/3, etc. É fácil para provar por indução que após n passos, a probabilidade de cada uma das cartas anteriores sendo o seleccionado um, é um / n.

Este usa o método lotes de números aleatórios, por isso é provavelmente mais lento do que a sua versão de duas passagens a menos ficando cada item é lento, ou avaliar os critérios é lento. Seria normalmente ser utilizado, por exemplo para a seleção de uma linha aleatória de um arquivo, onde você realmente não deseja executar sobre os dados duas vezes. Também é sensível ao viés nos números aleatórios.

É bom e simples, no entanto.

[Edit: prova

Seja p (j, k) ser a probabilidade de que o número do cartão j é o cartão seleccionado de momento após o passo k.

necessário para provar: para todo n, p (j, n) = 1 / N para todos 1 <= J <= n

Para n = 1, obviamente p (1,1) = 1, uma vez que o primeiro cartão é seleccionado no primeiro passo com probabilidade 1/1 = 1.

Suponha-se que p (j, k) = 1 / k para todos 1 <= j <= k.

Em seguida, seleccionar o (k + 1) -ésima cartão no passo (k + 1) com uma probabilidade de 1 / (k + 1), isto é, p (k + 1, k + 1) = 1 / (k + 1) .

Nós reter a seleção existente com probabilidade k / (k + 1), de modo que para qualquer j 

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

Então p (j, k + 1) = 1 / (k + 1) para todos 1 <= k <= k + 1

Assim, por indução, para todos os n: p (j, n) = 1 / N para todos 1 <= J <= n]

Outras dicas

Por que você não apenas manter uma outra coleção de cartões não utilizados?

Se você quer que eles em ordem aleatória, você pode primeiro embaralhe-os ( Fisher-Yates ), em seguida, pop-los fora como você precisar deles.

A melhor maneira de fazer isso é embaralhar as cartas em uma ordem aleatória, e depois escolher o primeiro cartão não utilizado. Aqui é a maneira mais comum para executar uma evasiva como esta.

O algoritmo padrão para lidar cartas aleatórias é.

  • inicializar o convés para conter todos os cartões (ordem não é importante)
  • loop:
  • Gerar índice aleatório no intervalo de 0 a plataforma-size - 1
  • placa de vídeo nesse índice (ou fazer o que quiser)
  • trocar cartão indexado no deck com o cartão em [baralho de tamanho -1]
  • reduzir baralho de tamanho por um
  • Goto loop: tantas vezes quanto necessário

Você poderia se livrar dos dois loops usando um 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];

Embora eu imaginaria o aumento da eficiência não seria grande, e você estará usando mais memória.

A outra opção seria a de ter duas listas, use um para rastrear os cartões usados ??e outro para controlar os cartões não utilizados. Então, se você usar um cartão, subtrai-lo a partir de listas de cartões não utilizados e adicioná-lo ao final da lista cartão utilizado. Dessa forma, você não terá que executar dois loops de cada vez.

Mantenha os cartões utilizados no final da matriz e os cartões não utilizados no início. Mantenha o controle de quantas cartas ainda não foram utilizados. Quando um novo cartão é usado, trocá-lo com o último cartão não utilizado e diminuir o 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--;

Eu não sei se isso vai produzir verdadeiramente aleatório estou empates, mas seria evitar loops através de toda a plataforma em quase todos os casos. Estou ainda menos certeza como seria comparar o desempenho sábio, mas aqui não deixa de ser:

  • obter carta aleatória do baralho
  • Se o cartão já é usado, escolher uma direção aleatória (para frente ou para trás)
  • passo através do convés da posição atual na direção aleatoriamente determinado até encontrar a próxima carta não utilizado (é claro que você tem que ter certeza que você está adequadamente enrolar nas extremidades do array)

Assim, no pior dos casos, você escolhe um cartão ao lado do último não utilizado e, em seguida, passo através do convés na direção 'errada', realizando assim um ciclo completo através do convés.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top