algoritmo de embaralhamento de Fisher-Yates

esse algoritmo é minha primeira contribuição ao “1001 algoritmos para implementar antes de morrer“, uma iniciativa do Karlisson Bezerra, autor do site/blog nerdson não vai à escola (passa lá, é excelente!). “primeira contribuição” porque pretendo fazer outras🙂

a proposta se resume a uma coleção de 1001 algoritmos (clássicos ou não) importantes (ou não) pra quem estuda programação.

decidi implementar o algoritmo de Fisher-Yates (solução de Durstenfeld) primeiramente porque eu gosto dele.  em segundo lugar, porque ele embaralha um vetor (óbvio), mas tem complexidade computacional O(n), tanto para o melhor quando para o pior caso. muitas, muitas implementações de embaralhamento por aí são probabilísticas, não tão boas assim, com complexidade O(n) para o melhor caso, O(((n-1)^2)/2) para o caso mais comum médio e O(∞) para o pior caso. sim, o pior caso é infinito (se não for garantido um sorteio justo).

implementação comum vs. Fisher-Yates

uma implementação muito comum de embaralhamentos que se vê por aí é:

  1. seja um número k igual ao primeiro elemento do vetor original;
  2. sortear um número x entre 1 e N, incluindo 1 e N;
  3. se x já tiver sido sorteado antes, repetir a partir do passo anterior;
  4. x é a nova posição k-ésimo elemento do vetor original em um vetor auxiliar aux;
  5. incrementar k;
  6. repetir do passo 1 até que k seja o último elemento do vetor original; este último elemento será posicionado na única posição ainda não foi sorteada;
  7. o vetor aux é o vetor original embaralhado;

essa implementação tem um sério problema; nos primeiros casos, dificilmente será necessário repetir o passo 2 . entretanto, à medida que mais e mais números são sorteados, fica mais difícil sortear um número que ainda não foi sorteado. quando só restarem dois elementos, a cada n sorteios que você fizer, n-2 serão para posições já sorteadas.

a grande sacada do algoritmo de Fisher-Yates (solução de Durstenfeld) é transformar sorteios repetidos em resultados diferentes. ela também não utiliza nenhum vetor auxiliar. acompanhe o passo-a-passo:

  1. gerar uma lista ordenada de N elementos
  2. sortear um número k entre 1 e N-1;
  3. trocar as posições dos elementos nas posições k e N;
  4. decrementar N;
  5. repetir do passo 2 até que N seja igual a 0;
  6. o vetor original estará embaralhado.

já foi postada no repositório oficial do projeto a implementação que eu fiz em C do algoritmo de embaralhamento de Fisher-Yates.  o código também está disponível no pastebin e você também pode vê-lo abaixo. como sempre, sugestões e críticas são muito bem vindas🙂

/*
Fisher–Yates shuffle, Knuth shuffle (Durstenfeld's Solution)
Autor:
    Ronald Fisher, Frank Yattes, Donald Knuth, Richard Durstenfeld
Colaborador:
    Anderson "Cacovsky" Marques Ferraz
    amarquesferraz@gmail.com
Tipo:
    sorting
Descrição:
    Embaralha um vetor de numeros sequenciais. Nao utiliza nenhum vetor
    auxiliar (in-place) e so realiza tantos sorteios quanto posicoes do
    vetor.
Complexidade:
    O(n)
Dificuldade:
    medio
Referências:
    http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
Licenca:
    LGPL
*/

#include <cstdio>
#include <cstdlib>
#include <ctime>

/**
  * gera uma lista ordenada
  */
int * gera_vetor_ordenado(int qtde_elementos)
{
    int *resultado= (int*) malloc(qtde_elementos*sizeof(int));

    for (int i=0; i<qtde_elementos; i++) resultado[i] = i;

    return resultado;
}

void imprime_vetor(int *vetor, int qtde_elementos )
{
    for (int i=0; i<qtde_elementos; i++) printf("%d ", vetor[i]);

    printf("\n");
}

int main()
{

    //setup
    int N = 10;
    int *elementos = gera_vetor_ordenado(N); //passo 1
    srand ( time(NULL) ); //inicializando a seed

    printf("Vetor ordenado: ");
    imprime_vetor(elementos, N);

    //core
    int elementos_restantes = N;
    while (elementos_restantes>0){
        int k = rand() % (elementos_restantes); //passo 2

        //passo 3
        int tmp = elementos[k];
        elementos[k] = elementos[elementos_restantes-1];
        elementos[elementos_restantes-1] = tmp;

        elementos_restantes--; //passo 4
    }

    printf("Vetor embaralhado: ");
    imprime_vetor(elementos, N);

    return 0;
}

4 Comentários on “algoritmo de embaralhamento de Fisher-Yates”

  1. Eder disse:

    Que coisa bunita eh um codigo em C

  2. Jairo Henrique disse:

    Não consigo ver aquele tipo de formatação de código de int main() sem sentir um calafrio… audfhiahdfiuahdfhaaai
    No mais, show de post!


Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s