Embaralhamento de Fisher-Yates em Java

Introdução

Um algoritmo simples e muito útil é aquele que permite embaralhar os elementos de um conjunto. Por exemplo, a sequência de números 2, 6, 5, 9, 8, após ser embaralhada, poderia se tornar 6, 8, 2, 9, 5. Uma aplicação prática para esse tipo de algoritmo é feita em jogos de cartas, onde uma pilha de cartas numa certa sequência é embaralhada e as cartas passam a ocupar posições aleatórias na pilha.

Nesta postagem será apresentada uma versão do algoritmo de embaralhamento de Fisher-Yates apresentada por Richard Durstenfeld em seu artigo "Algorithm 235: Random permutation" em 1964. O intuito é aplicar esse algoritmo para embaralhar elementos de um vetor baseado no índice da posição que cada elemento ocupa. Será usada a linguagem de programação Java na implementação.

Algoritmo de Fisher-Yates

O algoritmo de embaralhamento de Fisher-Yates consiste em realizar permutações num conjunto para que seus elementos assumam uma ordem aleatória. Além disso, uma das vantagens desse embaralhamento é que todas as possíveis ordens que o conjunto pode assumir são igualmente prováveis. Por exemplo, para um conjunto de 5 elementos existem 120 permutações diferentes (5! = 120), isto é, pode-se ordenar esses elementos de 120 formas diferentes e a probabilidade de cada uma dessas permutações é de 1/120 ou aproximadamente 0,83%.

A versão de Durstenfeld desse algoritmo para vetores com indexação iniciada por zero consiste nos seguintes passos:

1. Tome um vetor com "n" elementos de cujos índices vão de 0 até n - 1;
2. Seja "i" o índice da última posição, n - 1, sorteie um número aleatório "j" entre 0 e "i", incluindo 0 e "i";
3. Troque o elemento da posição "i" com o elemento da posição "j";
4. Decremente "i" (isto é, subtraia um de "i");
5. Repita os passos 2-4 enquanto "i" for maior que zero.

Após esses passos, o vetor estará embaralhado.

Observação: há um algoritmo de embaralhamento que, no passo 2, sorteia um número entre 0 e "n - 1" ao invés de 0 a "i". Entretanto, as ordens/permutações de elementos possíveis não são igualmente prováveis com tal algoritmo e algumas delas tem maior probabilidade de ocorrer. Portanto, não é um algoritmo justo (uma análise detalhada comparando esse algoritmo com o algoritmo de Fisher-Yates é feita no artigo da referência [2]).

Para exemplificar o algoritmo de Fisher-Yates, será usado o seguinte vetor com quatro elementos:

Na primeira linha temos os índices do vetor e na segunda linha temos os elementos armazenados nesse vetor. Pelo passo 2, i = 3, que é o índice da última posição. Então, sorteamos um número "j" entre 0 e 3. Suponha que o número sorteado seja j = 0. Assim, pelo passo 3, trocamos os elementos da posição i = 3 com j = 0:

Pelo passo 4, decrementamos "i", portanto i = 3 - 1 = 2. Pelo passo 5, repetimos os passos 2-4 enquanto "i" for maior que zero, assim:

Passo 2: i = 2, sorteamos um número "j" entre 0 e 2. Suponhamos que j = 1;

Passo 3: troque o elemento da posição i = 2 com j = 1:

Passo 4: decrementamos "i", portanto i = 2 - 1 = 1;

Passo 5: repetimos os passos 2-4 enquanto "i" for maior que zero;

Passo 2: i = 1, sorteamos um número "j" entre 0 e 1. Suponhamos que j = 1;

Passo 3: troque o elemento da posição i = 1 com j = 1:

Passo 4: decrementamos "i", portanto i = 1 - 1 = 0;

Passo 5: Como i = 0, então o algoritmo termina.

Logo, o vetor embaralhado será:

Observe que, a cada repetição dos passos 2-4, temos um elemento a menos para embaralhar. Observe também que quando i = 0 não faz sentido continuar repetindo os passos 2-4, pois, pelo passo 2, teríamos que sortear um número entre 0 e 0, que obviamente iria resultar em j = 0 e, pelo passo 3, iríamos trocar o elemento da posição 0 com ele mesmo, ou seja, seria redundante.

Implementação em Java

A implementação em Java a seguir utiliza um método auxiliar chamado swap, que troca a posição entre dois elementos de um vetor. Além disso, para sortear números aleatórios, utiliza-se um objeto da classe Random do Java. O método nextInt(int n) desse objeto sorteia um número inteiro entre 0 e n. Como esse método não inclui o "n" no sorteio, então basta somar um ao argumento "n" para que o mesmo seja incluso.

O download o código pode ser feito pelo link: ShuffleAlgorithm (Java).

/*
 * Autor: Henrique Felipe
 * https://www.blogcyberini.com/
 * Janeiro de 2015
 * 
 * "Algoritmo de embaralhamento (Fisher-Yates/Durstenfeld)"
 */

import java.util.Random;

public class ShuffleAlgorithm {
    //Teste

    public static void main(String[] args) {
        int g[] = {1, 2, 3, 4, 5, 6};
        shuffle(g);
        for (int i = 0; i < g.length; i++) {
            System.out.print(g[i] + " ");
        }
    }
    //"shuffle": este método embaralha os elementos do vetor especificado (Fisher-Yates/Durstenfeld).

    public static void shuffle(int[] a) {
        Random rnd = new Random();
        for (int i = a.length - 1; i > 0; i--) {
            int randomNumber = rnd.nextInt(i + 1);
            swap(a, i, randomNumber);
        }
    }
    //"swap": este método troca o elemento na posição 'i' do vetor com o elemento na posição 'j'. 

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

Referências

• [1] Fisher-Yates shuffle (Wikipédia). Disponível em: Fisher-Yates shuffle. Acesso em: 16 de janeiro de 2015.
• [2] NEDRICH, M. Fisher-Yates Shuffle - An Algorithm Every Developer Should Know. Acesso em: 16 de janeiro de 2015.