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:
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:
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/
Dæmonio Labs 
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+
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+
Blz Leandro ?
Estou com esse mesmo trabalho. Poderia me chama no WhatsApp pra gente troca uma ideia (meu numero : 31 995711579)
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!
Opa, Grato que tenha gostado Leandro.
Até mais
opa.
o código vai me ajudar muito, mas tenho uma duvida.
não entendi a parte de distribuir os vai-uns.
o que essa parte faz exatamente?
obrigado.
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:
Dê uma lida aí nesse post, e caso tenha dúvidas é só postar aqui nos comments, blz?
Daemonio
t+
Muito obrigado. está mais do que explicado. :)
Pingback: Gerando Permutações-r com Repetição em C | Daemonio Labs
Ó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
Gostaria de saber quais alterações eu teria que fazer se fosse usar um vetor de inteiros.
Qual é seu problema original? Sabendo dele fica melhor em ajudar.
Mas o vetor de inteiro precisa de um número que irá marcar o fim do vetor. Suponha que esse número seja o -1, então:
mude de:
char *vetor[] = {“pera”, “uva”, “maca”, “goaiaba”, NULL} ;
para:
int vetor[] = {0, 1, 3, 5, -1} ;
Onde os elementos são: 0, 1, 3 ,5 e o -1 marca o fim do vetor.
Por essa lógica, também trocar o NULL por -1 nas condicionais e também mudar o printf de saída.
Se você deseja um vetor alocado dinamicamente e/ou precisa ser preenchido via arquivo ou entrada de usuário, então você precisa adicionar mais código e chamá-lo logo no início da main.
E por que eu vou ler um N de um arquivo que vai ser os numero do meu vetor ( N ate 1) e depois vou ter que salva as permutações para eu poder compara-las depois.
Mas deu certo aqui muito obrigado, ótimo conteúdo, me ajudo muito.