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

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+

8 pensamentos sobre “Gerando Permutações com o Java

    • Olá Alex,

      Como uma permutação é um vetor de strings, para garantir a não repetição de elementos basta você percorrer o vetor a procura de elementos repetidos. Se houver repetição, a permutação não é mostrada na tela.

      Eu alterei a classe Main.java acrescentando esse conceito. Veja que agora há dois loops for para percorrer o vetor ‘saida’ em busca de repetição. O comando continue while_loop é usado para pular as permutações com repetição.

      Veja o código em:

      http://pastebin.com/f4ZV1asq

      Caso tenha alguma dúvida só postar aqui nos comentários.

      Abraços,
      Daemonio

  1. Ola Daemonio como seria o algorismo sem repetição mas verificando cada permutação, por exemplo jero uma permutação e antes de mandar para arrey de saida verifico se esta permutação serve para me
    Exemplo: todos 4+3*6 e presiso só permutasões que começa por dois numeros no arrey de saida
    43+*6 ou 43*6+….verificando cada permutação antes de mandar por arrey de saida para não fazer a função muito lenta
    Obrigada
    Daria

    • Olá Daria,

      Por esse método todas as permutações serão geradas e por isso ele tende a ser lento para um número grande de entrada. Para tornar o código um pouco mais rápido você terá que modificar a classe em si e colocar lá a condição para as permutações de saída.

      Pela descrição de seu problema, eu não entendi qual são as permutações que você deseja filtrar, mas de modo geral você terá que trocar a linha 45:

      de

      saida[j] = entrada[this.N[i]] ;

      por

      if ( … ) {
      saida[j] = entrada[this.N[i]] ;
      }

      Sendo que a condição do if é para filtrar as permutações desejadas. Por causa dessa modificação será necessário também mudar o código do método hasNext().

      Dependendo do número de combinações que você está gerando nem mesmo essas modificações irá agilizar a execução e se a velocidade for prioridade, aconselho usar outro algoritmo.

      Daemonio,
      t+

  2. Ola Daemonio obrigada que respondeste tão rapido….é muito deficil encontrar bom algoritmo de permutações no Net e como eu não sou capaz de escrever o bom codico estou a pedir tua ajuda

    Exemplo: tenho 4 numeros 1 2 3 4 e 4 sinais + – * / tenho de po-los nos 7 lugares 2+3+5-6
    sinais pode repetir-se numeros não
    ou seja
    1. tenho de criar arrey com todos permutações com repetição dos sinais
    2. depois juntando os numeros com sinais[0] criar todos permutações sem repetição mas guardar num arrey só aquelas que são em RPN (reverse polish notation) 23+45*- …
    ou seja só aquelas que nessesariamente tem 2 numeros nos primeiros dois lugares e o sinal nultimo lugar.
    3. juntar numeros com sinais[1] ….e assim por diante…….
    Sei que o problema um cado complicada…mas tenho grande esperansa que ajudas….já uma semana não consigo a resolver :(
    Na mesma grande obrigado Daemonio :)

    • Olá,

      Pelo que entendi, você tem que gerar três “conjuntos” de permutações: Uma para os números (sem repetição), uma para os sinais e uma para sinais+números. Para cada permutação de sinais você pega uma permutação de números e gera uma expressão, exemplo:

      uma permutação de sinais: +-/*
      uma permutação numérica: 2 3 4 5
      expressões possíveis:
      2 3 + 4 5 – * <– RPN
      5 + / 4 3 – 2 <– não é RPN
      etc
      etc
      etc

      Se for isso, eu acho que independente do algoritmo usado para gerar as permutações, a execução do seu programa irá demorar muito, porque você vai ter que gerar 4! (para os números) + 4^4 (para os sinais) + 8^4 (para as expressões) = 10240 permutações. Isso somente para o overhead gerado pelas permutações, não estou nem contando com os loops…

      Acho que você já sabe como resolver o seu problema, mas deve estar em dúvidas de como otimizá-lo. Mudar o algoritmo de geração de permutações não irá aumentar o desempenho de seu programa, por isso acho que você deve encarar seu problema de outra forma de modo que ele tenha o menor custo possível.

      Penso que seja isso. Se eu estiver errado é só comentar aqui. ;d

      Daemonio,
      t+

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