Codigo Em C Para Permutar Vetores

Introdução

Olhando as estatísticas do blog, percebi que muitas pessoas visitam o site procurando por uma implementação que permute os elementos de um vetor.

Para quem leu o post [1] aprendeu como gerar permutações com repetição de uma string de entrada. Hoje mostrarei como fazer permutações com e sem repetição em um vetor qualquer.

Permutações com repetição

O objetivo aqui é permutar os elementos de um vetor de tamanho n e gerar permutações de tamanho r. A idéia por trás do código não será mostrada aqui, pois ela já foi bem abordada no link [1].

Bem, o nome do programa é permrep.c e as instruções de compilação e execução se encontram no código fonte.

O Código

/*
 * [permrep.c]
 * Programa que gera permutacoes com repeticao
 * de um vetor.
 *
 * [Autor]
 * Marcos Paulo Ferreira (Daemonio)
 * undefinido gmail com
 * https://daemoniolabs.wordpress.com
 *
 * [Como compilar]
 * $ gcc -o permrep permrep.c
 *
 * [Como executar]
 * Basta digitar o nome do programa:
 * $ ./permrep
 *
 * Desse modo as permutacoes terao tamanho
 * n (quantidade de elementos do vetor). Para
 * fazer um n diferente de r, passe um parametro
 * para o programa:
 *
 * $ ./permrep 6
 *
 * Ira gerar permutacoes com tamanho 6.
 *
 * [Como setar o vetor]
 * O vetor que contem os elementos eh esse:
 *
 * char *vetor[] = {..., NULL} ;
 *
 * Coloque a quantidade de elementos que voce
 * desejar, mas lembre-se de botar um NULL
 * no fim, pois ele que indica o fim do vetor.
 *
 * Seg Ago 29 18:44:01 BRT 2011
 * Seg Ago 29 21:33:55 BRT 2011
 */
#include <stdio.h>
#include <stdlib.h>

/* Vetor de elementos. Coloque quantos elementos
 * quiser, mas o ultimo deve ser sempre NULL. */
char *vetor[] = {"pera",  "uva", "maca", "goaiaba", NULL} ;

int main(int argc, char **argv) {
    /* vetor que representara cada permutacao. */
    int *num ;
    /* quantidade de elementos do vetor. */
    int n ;
    /* tamanho de cada permutacao. */
    int r ;
    /* controle de loop. */
    int i, j ;

    /* Obtem a quantidade de elementos do vetor. */
    n=0;
    while ( vetor[n] != NULL ) n++ ;

    /* Testa parametros da linha de comando. */
    if ( argc > 1 ) {
        r = atoi(argv[1]) ;
    } else {
        r = n ;
    }

    /* Aloca espaco para o vetor num. Lembre-se
     * que o vetor `num' representa um numero
     * na base n com r algarismos. */
    num = (int *)calloc(r+1, sizeof(int)) ;
    if ( num == NULL ) {
        perror("malloc") ;
        return -1;
    }

    /* Inicio do algoritmo. */
    while ( num[r] == 0 ) {
        for(i=0; i < n; i++) {
            /* Mostra a permutacao na tela. */
            for(j=0; j < r; j++) {
                printf("%s ", vetor[num[j]]) ;
            }
            putchar('\n') ;

            /* incrementa o algarismo menos
             * significativo. */
            num[0]++ ;
        }

        /* distribui os vai-uns. */
        for(i=0; i < r; i++) {
            if(num[i] == n) {
                num[i] = 0;
                num[i+1]++ ;
            }
        }
    }

    free(num) ;

    return 0;
}

Se o wordpress bagunçar o código então é mais seguro baixá-lo diretamente pelo link:

Download permrep.c(.docx)

Exemplo de execução

Sendo:

char *vetor[] = {"pera",  "uva", "maca", "goaiaba", NULL} ;

e executando o programa assim:

$ ./permrep 3 | head -n 10

temos a saída truncada para 10 linhas:

pera pera pera
uva pera pera
maca pera pera
goaiaba pera pera
pera uva pera
uva uva pera
maca uva pera
goaiaba uva pera
pera maca pera
uva maca pera

O total de permutações é dado por: n^r. Então para n=4 e r=3 o total é de: 4^3 = 64.

Permutações sem repetição

Para que as permutações contenham somente uma instância de cada elemento, o vetor num não pode conter números repetidos. A diferença desse código em relação ao anterior é que agora temos a função eh_sem_repeticao() que retorna verdadeiro quando num contém elementos distintos. Somente nessa ocasião que uma permutação em particular será mostrada na tela.

Bem, o nome do programa é permnorep.c e as instruções de compilação e execução se encontram no código font.

O Código

/*
 * [permnorep.c]
 * Programa que gera permutacoes sem repeticao
 * de um vetor.
 *
 * [Autor]
 * Marcos Paulo Ferreira (Daemonio)
 * undefinido gmail com
 * https://daemoniolabs.wordpress.com
 *
 * [Como compilar]
 * $ gcc -o permnorep permnorep.c
 *
 * [Como executar]
 * Basta digitar o nome do programa:
 * $ ./permnorep
 *
 * Desse modo as permutacoes terao tamanho
 * n (quantidade de elementos do vetor). Para
 * fazer um n diferente de r, passe um parametro
 * para o programa:
 *
 * $ ./permnorep 6
 *
 * Ira gerar permutacoes com tamanho 6.
 *
 * Detalhe: Sempre escolha um valor de r menor
 * que n, pois se r > n a permutacao sempre
 * tera repeticao e nada sera mostrado na tela.
 *
 * [Como setar o vetor]
 * O vetor que contem os elementos eh esse:
 *
 * char *vetor[] = {..., NULL} ;
 *
 * Coloque a quantidade de elementos que voce
 * desejar, mas lembre-se de botar um NULL
 * no fim, pois ele que indica o fim do vetor.
 *
 * Seg Ago 29 18:44:01 BRT 2011
 * Seg Ago 29 21:55:30 BRT 2011
 */
#include <stdio.h>
#include <stdlib.h>

/* Vetor de elementos. Coloque quantos elementos
 * quiser, mas o ultimo deve ser sempre NULL. */
char *vetor[] = {"pera",  "uva", "maca", "goaiaba", NULL} ;

/* Funcao que retorna verdadeiro se
 * `num' nao contem algarismos repetidos
 * e zero caso contrario. */
char eh_sem_repeticao(int *num, int r) {
    int i, j ;

    for(i=0; i < r; i++) {
        for(j=0; j < r && i != j; j++) {
            if(num[i] == num[j]) {
                return 0;
            }
        }
    }

    return 1 ;
}

int main(int argc, char **argv) {
    /* vetor que representara cada permutacao. */
    int *num ;
    /* quantidade de elementos do vetor. */
    int n ;
    /* tamanho de cada permutacao. */
    int r ;
    /* controle de loop. */
    int i, j ;

    /* Obtem a quantidade de elementos do vetor. */
    n=0;
    while ( vetor[n] != NULL ) n++ ;

    /* Testa parametros da linha de comando. */
    if ( argc > 1 ) {
        r = atoi(argv[1]) ;
    } else {
        r = n ;
    }

    /* Sai do programa se r > n. */
    if ( r > n ) {
        printf("Nao faz sentido r > n.\n") ;
        return -1 ;
    }

    /* Aloca espaco para o vetor num. Lembre-se
     * que o vetor `num' representa um numero
     * na base n com r algarismos. */
    num = (int *)calloc(r+1, sizeof(int)) ;
    if ( num == NULL ) {
        perror("malloc") ;
        return -1;
    }

    /* Inicio do algoritmo. */
    while ( num[r] == 0 ) {
        for(i=0; i < n; i++) {
            /* Mostra a permutacao na tela se
             * e somente se `num' nao contem
             * algarismos repetidos. */
            if ( eh_sem_repeticao(num, r) ) {
                for(j=0; j < r; j++) {
                    printf("%s ", vetor[num[j]]) ;
                }
                putchar('\n') ;
            }

            /* incrementa o algarismo menos
             * significativo. */
            num[0]++ ;
        }

        /* distribui os vai-uns. */
        for(i=0; i < r; i++) {
            if(num[i] == n) {
                num[i] = 0;
                num[i+1]++ ;
            }
        }
    }

    free(num) ;

    return 0;
}

Se o wordpress bagunçar o código então é mais seguro baixá-lo diretamente pelo link:

Download permnorep.c(.docx)

Exemplo de execução

Sendo:

char *vetor[] = {"pera",  "uva", "maca", "goaiaba", NULL} ;

e executando o programa assim:

$ ./permnorep 3 | head -n 10

temos a saída truncada para 10 linhas:

maca uva pera
goaiaba uva pera
uva maca pera
goaiaba maca pera
uva goaiaba pera
maca goaiaba pera
maca pera uva
goaiaba pera uva
pera maca uva
goaiaba maca uva

O total de permutações é dado por: n*(n-1)*(n-2)*…*(n-r+1) => n!/(n-r)!. Então para n=4 e r=3 o total é de: 4!/(4-3)! = 4! = 24.

Observações

Para valores altos de n e r o programa poderá demorar a mostrar a saída na tela. Isso ocorre porque a função printf() bufferiza os dados antes de mandar para a saída padrão. Se isso for problema para você, tente usar um flush(stdout) depois de cada printf() para contornar esse problema.

Referências

[1] Gerando Permutações-r com Repetição em C by Daemonio (Acessado em: Agosto/2011)
https://daemoniolabs.wordpress.com/2011/02/11/gerando-permutacoes-r-com-repeticao-em-c/

12 pensamentos sobre “Codigo Em C Para Permutar Vetores

  1. Cara, tem como alterar esse codigo de permutação sem repetição, pra no caso, eu inserir a quantidade N, preencher as N posições com 1, 2 … N sem esse lance de R, e sem os argumentos argv e argc? Tipo, considerando que serão inseridas apenas números diferentes? Tem como me ajudar?

    • Ok! Coloquei a rotina para ler o vetor usando a entrada padrão. Você irá digitar cada elemento de
      uma vez e no final deverá digitar “fim” (sem aspas) para o programa interromper a leitura.

      Em relação ao r, aqui ele será sempre igual a n (quantidade de elementos da entrada).

      Veja o código em:

      http://pastebin.com/EayQEcRt

      Daemonio,
      t+

  2. Opa, tudo bem de novo? Obrigado pelo código ^^ mais uma coisa, eu não consegui alterar uma coisa nele. Tipo, voce criou uma matriz de char pra guardar em cada linha um vetor diferente, certo? Então, concorda comigo que a quantidade de vetores diferentes é (n-1)!?
    Então, eu tentei criar uma matriz de INTEIROS (mudar a de char que voce criou), com (n-1)! linhas, salvo em N, e com n colunas, inseridas pelo usuário. Assim, eu tentei fazer que cada vetor impresso fosse colocado em uma linha da matriz (a matriz de inteiro N x n, pois mais tarde, no meu código, eu vou precisar de cada vetor (no caso, cada linha da matriz), salvo na matriz de inteiros. Isso é pro meu trabalho de Caixeiro Viajante, onde em cada vetor permutado, eu vou acessar a matriz de distancias que calculei em outra função, e somar a distancia pra cada vetor permutado, e imprimir o que tem menor distancia, ou seja, a melhor solução. Entende minha situação? Tem como me ajudar novamente?

    • Entendo sim. Já tive que implementar uma heurística gulosa do Caixeiro Viajante e fiz exatamente o que você está fazendo (fiz em Java porque achei que em C seria pedreira :D).

      Fiz um código aqui que deve te ajudar. Ele gera as permutações de um conjunto de elementos e as armazena numa matriz, com isso todas as permutações podem ser recuperadas bastando acessar a matriz.

      http://pastebin.com/Ynb1PftV

      O código está simples e abstrai muitos detalhes que você irá encontrar em sua implementação. Veja que declarei o vetor como sendo [121][5] e que 121 é o total de permutações (+ 1 porque o elemento 0 guarda os dados de entrada). Em casos gerais, o ideal é declarar uma matriz dinâmica e depois ir reallocando as posições para cada permutação gerada. Mas aí já é contigo ;D

      Espero que seja isso. Fique à vontade para comentar.

      Daemonio,
      t+

  3. Nossa cara, muito obrigado mesmo! Ajudou muito, você nem imagina. Já peguei esse código e fiz as devidas modificações, em relação a alocação dinamica e tudo mais, e a leitura pelo teclado. Está funcionando perfeitamente! Muito obrigado, de novo. Blog show de bola!

    • Olá Felipe,

      Então, o algoritmo funciona mais ou menos assim: você cria um vetor de r posições, sendo que r é o tamanho da permutação desejada. Esse r existe para tornar possível, por exemplo, gerar permutações de tamanho 3 com 10 elementos.

      Bem, cada posição desse vetor contém um número que nada mais é que um índice referenciando um elemento da entrada. Suponha que você queira permutar um total de 6 elementos, então nesse caso n=6 e os elementos da entradas são referenciados pelos números: 0, 1, 2, 3, 4, 5.

      Inicialmente o vetor criado é preenchido com zeros e para cada permutação gerada, o último elemento é incrementado de 1. O que era zero virou um, o que era um virou dois, …, e o que era cinco virou? Como cinco é o último índice válido então a contagem deve começar novamente e é nesse momento que você zera essa posição do vetor e incrementa a posição seguinte, como se um vai-um da matemática tivesse ocorrido.

      O que expliquei foi a grosso modo, mas você pode pegar uma explicação melhor aqui:

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

      Dê uma lida aí nesse post, e caso tenha dúvidas é só postar aqui nos comments, blz?

      Daemonio
      t+

  4. Pingback: Gerando Permutações-r com Repetição em C | Daemonio Labs

  5. Ótimo artigo. Usei esse de Permutação com Repetição para um Método Exato que encontra a menor soma de cores e o menor número de cores necessárias para se colorir um grafo. Seria bacana se você colocasse permutações utilizando recursão. Valeu pelo Ensino. =)

    • Olá Simone,

      fico feliz que tenha gostado do artigo. Futuramente, eu farei algo sobre como gerar permutações e combinações usando recursão. Obrigado pela dica.

      Abraços

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