Gerando Permutações com o Java

Introdução

Como esses dias postei a classe java para as Combinações[1] então resolvi postar uma classe para as Permutações. Como vimos em:

https://daemoniolabs.wordpress.com/2011/02/11/gerando-permutacoes-r-com-repeticao-em-c/

Gerar permutações não é nada difícil em C e em Java muito menos. Para mais detalhes de implementação, veja o link acima.

Classe: Permutacao.java

/**
 * Classe que define as operacoes de Permutacoes
 * vistas em:
 *
 * https://daemoniolabs.wordpress.com/2011/02/11/
 * gerando-permutacoes-r-com-repeticao-em-c/
 *
 * Qualquer dúvida visite o post acima para obter
 * mais explicações.
 *
 * Autor: Daemonio (Marcos Paulo Ferreira)
 * Contato: undefinido gmail com
 * https://daemoniolabs.wordpress.com
 *
 * Fri Jul  8 10:16:07 BRT 2011
 */
package permutacao;

public class Permutacao {
    private int[] N ;
    private int n ;
    private String[] entrada ;
    private int r ;

    /**
     * entrada é seu vetor de elementos e r
     * é o tamanho da permutacao. Aqui r obrigatoriamente
     * deve ser maior que zero.
     */
    public Permutacao(String[] entrada, int r) {
        this.r = r ;
        this.n = entrada.length ;
        this.N = new int[r+1] ;
        this.entrada = entrada ;
    }

    public boolean hasNext() {
        return this.N[this.r] == 0 ;
    }

    public String[] next() {
        String[] saida = new String[this.r] ;
        int i, j ;

        for(i=0, j=this.r-1; i < this.r; i++) {
            saida[j] = entrada[this.N[i]] ;
            j-=1 ;
        }

        this.N[0] += 1 ;

        for(i=0; i < this.r; i++) {
            if(this.N[i] == this.n) {
                this.N[i] = 0;
                this.N[i+1] += 1 ;
            }
        }
        return saida ;
    }
}

Teste de Execução

Usando a classe abaixo (Main.java) podemos testar a classe Permutacao.java:

/**
 * Classe teste para ver os resultado das permutacoes.
 *
 * Autor: Daemonio (Marcos Paulo Ferreira)
 * Contato: undefinido gmail com
 * https://daemoniolabs.wordpress.com
 *
 * Fri Jul  8 10:16:07 BRT 2011
 */
package permutacao;

/**
 *
 * @author daemonio
 */
public class Main {
    public static void  main(String[] args) {
        String[] str =  {"uva", "pera", "laranja", "manga", "goiaba"};
        String[] saida ;

        /**
         * Primeiro parametro: O vetor de elementos
         * Segundo parametro:  O tamanho de r. Esse tamanho
         * deve ser maior que zero.
         */
        Permutacao p = new Permutacao(str, 3) ;

        while (p.hasNext()) {
            saida = p.next();

            for ( String e : saida ) {
                System.out.print(e + ",") ;
            }
            System.out.println() ;
        }
    }
}

A saída para a execução acima será:

Saida da Permutacao

Nem toda saída está na imagem acima. pois o resultado foi de 5^3 = 125 permutações.

Alguns detalhes:

1) O código está bem simples, fiz o mínimo para ele ser funcional.

2) O tamanho de r deve ser maior que zero.

3) O total de saídas será o tamanho do vetor elevado a r. Um vetor de 7 elementos e um r igual a 5 irá gerar 7^5= 16807 saídas, que para mim é muita coisa. Por precaução manere nos valores de r e no tamanho do vetor.

4) Qualquer dúvida sobre implementação, poste nos comentários ou reveja o link explicando como gerar as permutações.

Veja também:

[1] Gerando Combinações Usando Java
https://daemoniolabs.wordpress.com/2011/07/04/gerando-combinacoes-usando-java/

Sem mais. t+