Gerando Permutações-r com Repetição em C

Introdução

Nesse post você aprenderá uma maneira fácil de gerar permutações-r de um conjunto. Métodos de se gerar permutações são muitos comuns em programação e suas aplicações são diversas. Um exemplo é para gerar wordlists para um ataque de Brute Force.

No fim do post há um código em C de um programa exemplificando os conceitos vistos aqui.

Definições

Antes de tudo, vamos ver o que é cada coisa:

Permutação: é o arranjo de elementos distintos de um conjunto. Se esse conjunto for [1,2,3] então a permutação de seus elementos resultará em: [1,2,3], [1,3,2], [3,1,2], [3,2,1], [2,3,1], [2,1,3].

Permutação com repetição: é a permutação acima, mas com a possibilidade de repetição de elementos. Para o conjunto [1,2,3], os agrupamentos possíveis seriam: [1,2,3], [1,3,2], [3,1,2], [3,2,1], [2,3,1], [2,1,3], [1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,1,3], [1,3,1], [3,1,1], [2,2,2], [2,2,1], [2,1,2], [1,2,2], [2,2,3], [2,3,2], [3,2,2], [3,3,3], [3,3,1], [3,1,3], [1,3,3],[3,3,2], [3,2,3], [2,3,3].

Permutação-r: nesse tipo de permutação podemos entrar com um r para indicar a quantidade de elementos dos agrupamentos. Na primeira definição o conjunto tem 3 elementos, assim como os agrupamentos resultantes, dessa forma é como se o r fosse igual a 3. Suponha novamente o conjunto [1,2,3] só que agora a quantidade de elementos de cada agrupamento é 2, ou seja: r=2. Os agrupamentos finais seriam: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2].

Permutações-r com repetição: é esse tipo de caso que veremos aqui. É o mesmo que gerar as permutações-r só que incluindo os agrupamentos com elementos repetidos. Para o conjunto [1,2,3] e r=2, os agrupamentos finais seriam: [1,1], [1,2], [1,3], [2,2], [2,1], [2,3], [3,3], [3,1], [3,2].

Para facilitar, usarei o termo permutação ou permutação-r para referenciar esse último caso.

Para as permutações-r com repetição a quantidade de agrupamentos será n^r. Sem muita matemática é fácil chegar nessa fórmula. Pense que para cada posição de um elemento, tem-se n possibilidades. Como temos r posições, a quantidade final é de:

n * n * n * n * ... * n = n^r.
\_________ ___________/
          v
       r vezes

Processo de contagem

O processo de contagem para uma base é a disposição de seus símbolos para representar as quantidades numéricas em ordem crescente, começando do zero. Utilizando a base 10, a contagem para os primeiros 15 símbolos é:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

O interessante aqui é a mudança de casa. Repare na passagem do 9 para o 10. O ‘9’ virou ‘0’ (zero) e um vai um foi propagado, ocupando a casa das dezenas e formando o número 10. A próxima mudança de casa ocorre com o 99 e neste caso o “99” vira “00” e o vai um incrementa a posição à esquerda, formando o número 100.

Veja que isso ocorre para qualquer base. Para a base 3, por exemplo, a mudança de casa ocorre quando se incrementa o número 2, como em 22 + 1 = 100. Para uma base n, essa mudança ocorre no incremento do algarismo n-1.

O conceito de processo de contagem para uma base n, nada mais é que a geração das permutações-r dos símbolos dessa base, como veremos no próximo tópico.

Permutação-r para símbolos numéricos

Quando contamos números na base 10, o que realmente estamos fazendo é gerando as permutações-r para os algarismos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Se pegarmos todos os números antes do 99, isso é, 00, 01, 02, .., 10, .., 20, .., 50, .., 60, .., 80, .., 98, 99, vemos que, em termos de permutações, estamos gerando todos os agrupamentos possíveis dos 10 algarismos da base 10 com o r igual a 2 (conferindo: 10^2 = 100, ok!). Suponha agora os números entre 000 e 999, isso é, 000, 001, …, 999. Eles nada mais são que as permutações-r dos símbolos [0-9] para r=3.

Isso nos mostra que, para gerar permutações-r de n símbolos numéricos, basta obter todos números de r algarismos da base n.

Permutação-r para qualquer símbolo 

Se cada número de r algarismos em uma base n é uma permutação-r dos símbolos dessa base, como podemos utilizar esse conceito para símbolos não numéricos? A resposta é: fazendo mapeamento.

Suponha que se deseja gerar permutações-r do conjunto {“uva”, “banana”, “abacaxi”}. Para um r=3, tudo que se precisa fazer é gerar todos os números de r=3 algarismos da base 3 e em seguida, mapear o símbolo 0 em “uva”, o 1 em “banana” e o 2 em “abacaxi”. Veja:

000 -->  uva, uva, uva
001 -->  uva, uva, banana
002 -->  uva, uva, abacaxi
010 -->  uva, banana, uva
011 -->  uva, banana, banana
012 -->  uva, banana, abacaxi
020 -->  uva, abacaxi, uva
021 -->  uva, abacaxi, banana
022 -->  uva, abacaxi, abacaxi
100 -->  banana, uva, uva
101 -->  banana, uva, banana
...
222 --> abacaxi, abacaxi abacaxi

Podemos ver que o processo é bem simples. Só precisamos saber como gerar os números em uma base n e mapeá-los em nosso conjunto preestabelecido.

Código

Abaixo um código em C para gerar as permutações-r com repetição para um determinado conjunto de entrada. Para facilitar, o programa só gerará permutações de caracteres. Para se trabalhar com strings, seria necessário um vetor para armazená-las, o que complicaria o código que eu desejo deixar o mais didático possível. Para permutar strings, como “uva”, “banana” e “abacaxi”, veja a referência [2].

/*
 * [dperm.c]
 * Gera permutações-r com repetição dos caracteres
 * dados na entrada.
 *
 * [Autor]
 * Marcos Paulo Ferreira (Daemonio)
 * undefinido gmail com
 * https://daemoniolabs.wordpress.com
 *
 * [Uso]
 * $ gcc -o dperm dperm.c
 * $ ./dperm
 *   digite caracteres
 *   digite o r
 *
 * [Exemplo]
 * $ ./dperm
 *   Entre com o conjunto inicial: abcd
 *   Entre com o r: 3
 *   aaa
 *   aab
 *   aac
 *   aad
 *   aba
 *   ...
 *   etc
 *   ...
 *
 * Versão 1.0, by daemonio @ Fri Feb 11 00:36:35 BRST 2011
 * Versão 1.1, by daemonio @ Tue Jul 24 23:09:33 BRT 2012
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Tamanho máximo da string de entrada. */
#define MAX 250

int main() {
    /* Nosso número na base n. Ele é um vetor
     * de n+1 posições representando um número
     * na base n.
     */
    int *num ;
    /* input é a string de entrada, e str
     * receberá cada permutação.
     */ 
    char input[MAX], str[MAX] ;
    int n, r, i, j, k ;

    printf("Entre com o conjunto inicial: ") ;
    scanf("%s", input) ;

    printf("Entre com o r: ") ;
    scanf("%d", &r) ;

    /* Aqui elimina-se caracteres repetidos na entrada.
     * Esse procedimento não faz parte do algoritmo, e
     * só é feito por questões práticas.
     */
    n = strlen(input) ;
    j = 0;
    str[0] = 0 ;
    for ( i = 0; i < n; i++ ) {
        if ( strchr(str, input[i]) == NULL ) {
            str[j] = input[i] ;
            j++ ;
            str[j] = 0 ;
        }
    }
    strcpy(input, str) ;
    n = strlen(input) ;

    /* Cria o nosso número. Ele é um vetor de
     * r+1 posições, sendo que a última é 
     * reservada para indicar quando todos os
     * números de tamanho r foram gerados. */
    num = (int *) calloc( (r+1), sizeof(int)) ;
    if ( num == NULL ) {
        perror("calloc") ;
        return -1;
    }

    /* Termina quando a última posição do vetor
     * for 1. */
    while ( num[r] == 0 ) {
        for ( i = 0; i < n; i++ ) {
            /* processo de mapeamento. */
            for ( j = 0, k = r-1; j < r; j++ ) {
                str[k] = input[num[j]] ;
                k-- ;
            }
            /* Mostra o resultado. */
            str[r] = 0 ;
            printf("%s\n", str) ;

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

        /* Muda de "casa" e lança os vai uns. */ 
        for ( i = 0; i < r; i++ ) {
            if ( num[i] == n ) {
                num[i] = 0 ;
                num[i+1]++ ;
            }
        }
    }

    return 0 ;
}

Compilando e usando

Para compilar é fácil. Salve o código como dperm.c e digite:

$ gcc -o dperm dperm.c

O programa dperm foi gerado. Vamos executá-lo:

$ ./dperm
Entre com o conjunto inicial: abc
Entre com o r: 2
aa
ab
ac
ba
bb
bc
ca
cb
cc

Mais detalhes se encontram no fonte do programa.

Explicando o código

1) O código começa fazendo a leitura do conjunto de entrada e do r. O conjunto pode ser uma string qualquer e o r deve ser um inteiro maior ou igual a 1.

2)

n = strlen(input) ;
    j = 0;
    str[0] = 0 ;
    for ( i = 0; i < n; i++ ) {
        if ( strchr(str, input[i]) == NULL ) {
            str[j] = input[i] ;
            j++ ;
            str[j] = 0 ;
        }
    }

    strcpy(input, str) ;
    n = strlen(input) ;

Essa parte elimina os caracteres repetidos da string. Devemos ter esse tipo de código, pois a entrada deve conter elementos distintos.

3)

    num = (int *) calloc( (r+1), sizeof(int)) ;
    if ( num == NULL ) {
        perror("calloc") ;
        return -1;
    }

Esse código aloca r+1 posições para um vetor que irá representar nosso número. É mais prático trabalhar com um vetor em que cada posição é um algarismo do que trabalhar com um número inteiro de fato. A todo momento precisamos acessar uma posição específica de um único algarismo, e isso é mais fácil de ser feito com indexação de vetores.

Bem, o calloc foi usado porque além de obter memória na heap, essa função também preenche com zeros esse novo espaço de memória. Como vimos, o vetor terá r+1 posições, sendo que essa última posição será usada para indicar quando todos os números já foram gerados.

4)

    while ( num[r] == 0 ) {

O num[r] indexa a última posição do vetor que é usada como flag para término do processo.

5)

        for ( i = 0; i < n; i++ ) {
            num[0]++ ;
        }

Esse loop mais externo é o que incrementa o algarismo menos significativo. Esse algarismo é incrementado até o valor n-1, onde n é a base do número (ex: na base 8, o valor limite é 8-1=7).

6)

            for ( j = 0, k = r-1; j < r; j++ ) {
                str[k] = input[num[j]] ;
                k-- ;
            }

            str[r] = 0 ;
            printf("%s\n", str) ;

Aqui mapeamos cada posição de nosso vetor número em um elemento válido do conjunto de entrada. No fim do loop, o novo agrupamento estará na string str.

7)

        for ( i = 0; i < r; i++ ) {
            if ( num[i] == n ) {
                num[i] = 0 ;
                num[i+1]++ ;
            }
        }

Aqui realizamos o processo de mudança de casa e propagação de vai uns. Em outras palavras: todas as posições iguais a n devem ser setadas para 0, e ao mesmo tempo a posição à esquerda (i+1) deve ser incrementada.

Conclusão

Particularmente gostei desse método de gerar permutações-r por ser leve e rápido. Usamos apenas estruturas simples de loops e vetores para elaborar todo o código.

Uma aplicação de permutações é para se gerar wordlists, como um passo inicial para um ataque de Brute Force. Para mais detalhes, veja o script brutus.sh em [3].

Referências

[1] r-Permutations With Repetitions by phoxis (Acessado em: Julho/2012)
http://phoxis.org/2009/08/01/rpermrep/

[2] Código Em C para Permutar Vetores by Daemonio (Acessado em: Julho/2012)
https://daemoniolabs.wordpress.com/2011/08/30/codigo-em-c-para-permutar-vetores/

[3] Shell Script Para Ataques Brute Force by Daemonio (Acessado em: Julho/2012)
https://daemoniolabs.wordpress.com/2011/07/28/shell-script-para-ataques-brute-force/

22 pensamentos sobre “Gerando Permutações-r com Repetição em C

  1. Pingback: Gerando Permutações com o Java | Daemonio Labs

  2. Pingback: Shell Script Para Ataques Brute Force | Daemonio Labs

  3. Pingback: Codigo Em C Para Permutar Vetores | Daemonio Labs

  4. Pingback: Conversão de base numérica | Daemonio Labs

  5. Post editado em: 25/07/2012.

    O post anterior (publicado há um ano) estava muito bagunçado e com leitura difícil. Nessa nova revisão fiz de tudo para tornar a linguagem mais clara.
    Caso encontrem algum erro ou estiverem com dúvidas sobre o assunto, postem nos comentários.

    Abraços.

  6. Olá Erickson,

    basta você entrar com a string contendo j M’s e c V’s. Se entendi direito, para j=3 e c=4 então a string deve ser MMMVVVV.

    Como o código retira caracteres repetidos, você vai ter que retirar esse bloco de código para aceitar sua string:

    n = strlen(input) ;
    j = 0;
    str[0] = 0 ;
    for ( i = 0; i < n; i++ ) {
    if ( strchr(str, input[i]) == NULL ) {
    str[j] = input[i] ;
    j++ ;
    str[j] = 0 ;
    }
    }
    strcpy(input, str) ;

    comente ou delete esse pedaço código para funcionar com strings com caracteres repetidos.

    Abraços!

  7. Daemonio,

    Qual a melhor maneira e implementar este código para ele combinar valores unitários que possuem mais de 1 caractere? EX: Combinar os numeros 23, 24 e 25. Da maneira que está, ele vai considerar 2, 3, 4 e 5.

    Abraços!

  8. queria saber como posso modificar o código para ele fazer um indice lexicográfico, onde estão listadas todas as palavras formadas de 1 a 5 caracteres permutadas de A até Z. Eai eu entraria com uma palavra, exemplo: abcde e ele retornaria o indice dessa palavra, de acordo com o índice que eu criei, começando do A – indice 1, B – indice 2…. Z – indice 26 AB – indice 27 …. ZY indice xx e assim por diante até ficar com 5 caracteres e permutar todas as 26 letras.

  9. Para fazer um indice lexicografico, com todas as letras do alfabeto primeiramente, depois adicionando ao A a letra seguinte (AB) e depois com C…. Até Z, e ai adicionar mais um letra, isto é ABC, ABD, ABE… e assim por diante ate 5 letras, permutadas e sem repeticação, como AAAA por exemplo. No caso teria que ler de um arquivo texto e conferir no indice se a palavra está inserida, se estiver tenho que mostrar a palavra e o indice no formato palavra -> indice. Por exemplo, se no arquivo tiver a b c ab, saida teria que ser:
    a -> 1
    b -> 2
    c -> 3
    ab -> 27 (seria logo após o z)

    • Parece que a sequência de letras é só mais uma representação de um número na base 26. O “número”:

      ab

      equivale a:

      12 (base 26)

      (isso é: a=1 e b=2)

      que na base 10 tem valor:

      1 * 26^1 + 2*26^0 = 28

      No seu caso deu 27 porque você desconsiderou o “aa” que também é um número válido.

      Basicamente é só seguir o algoritmo apresentado e mostrar a permutação formada antes do ‘->’ e mostrar o vetor num[] na base 10 após o ‘->’.

      O único cuidado vai ser em relação aos números duplicados. A solução, a principio, seria contar quantos deles apareceram e subtrair do valor de num[]. No exemplo “ab” o único duplicado que apareceu antes dele foi o “aa”, logo o valor final será 28-1 = 27.

      Abraços

      • Mas daemonio, fazendo os calculos para o exemplo do meu professor: vwxyz -> 83681 (este parece que seria o ultimo elemento)

        seria v -> 22
        w -> 23
        x -> 24
        y -> 25
        z -> 26

        fazendo a conversão ficaria: 22*26^4 + 23*26^3 + 24*26^2 + 25*26^1 + 26*26^0 = 10474619 , onde deveria dar os 83681. Há algum calculo que não estou fazendo certo?

        aqui esta o enunciado:
        Contexto
        Os esquemas de codificação são geralmente usados em situações que requerem criptografia ou economia na transmissão e armazenamento de informações.
        Considere o seguinte esquema de codificação para palavras de um dado alfabeto.
        O alfabeto é o conjunto de letra minúsculas {a, b, c, …, v, w, x, y, z}.
        Usando este alfabeto, são consideradas válidas as palavras de 1 até 5 letras que estejam em ordem lexicográfica estrita. Isto é, toda letra é estritamente maior que sua antecessora na ordem lexicográfica. Por exemplo, as palavras elmo, gk e itu são válidas, enquanto as palavras
        casa, aab e nada não são válidas.
        Nosso esquema de codificação é construído associando a cada palavra válida um inteiro que indica a posição da palavra na lista de palavras, que é ordenada segundo o tamanho e a ordem lexicográfica das palavras (para palavras de mesmo tamanho). Isto é:
        a -> 1
        b -> 2

        z -> 26
        ab -> 27
        ac -> 28

        az -> 51
        bc -> 52

        vwxyz -> 83681

        Descrição
        Escreva um programa que leia um arquivo texto contendo uma série de palavras. Para cada palavra do arquivo, seu programa deve imprimir, em uma linha separada, a palavra lida seguida do índice correspondente (calculado segundo o esquema de codificação acima), se a palavra
        for válida.
        Seu programa deve imprimir a palavra seguida do zero, se a palavra for inválida.
        Assunções e restrições
        1. O nome do arquivo é palavras.txt. Considere que ele estará no mesmo diretório em que o
        programa for executado.
        2. O arquivo conterá no mínimo uma palavra.
        3. Cada linha do arquivo pode conter zero ou mais palavras (isto é, pode haver linhas vazias ou apenas com espaços).
        4. Cada palavra gravada no arquivo pode ter de 1 (um) a 30 (trinta) caracteres, todos minúsculos. Os caracteres são codificados no padrão ASCII.
        5. São inválidas tanto as palavras que não sigam estritamente a ordem lexicográfica,
        quanto as que possuem mais de cinco letras ou contêm letras fora do alfabeto.
        6. A impressão deve seguir o seguinte formato: pal -> ind
        onde pal é a palavra lida e ind é o índice correspondente (ou zero).
        Exemplo A)
        Considere que o arquivo palavras.txt contenha as seguintes linhas:
        2 / 3
        Índice lexicográfico (arquivo texto)
        z a
        urso
        vwxyz b
        Então, seu programa deve produzir a seguinte saída:
        z -> 26
        a -> 1
        urso -> 0
        vwxyz -> 83681
        b -> 2

      • Lucas,

        informei errado. Os símbolos vão de 1 a 26 logo a base é 27 e não 26. Com isso, o certo é fazer ab=1*27^1+2*27^0.

        Eu disse que era para fazer isso e depois retirar os inválidos, porém, existe outra restrição no seu exercício que é a manutenção da ordem lexicográfica dos símbolos. Logo, além de retirar os inválidos (letras repetidas) é necessário também retirar as strings que não respeitam a ordem lexicográfica.

        Fiz um código que gera todas as sequências e também informa o valor. Testei com os valores que você me deu e bateu direitinho.

        Agora só adaptá-lo para seu TP. Acredito que você deve ler uma palavra, gerar TODA a sequência até essa palavra e obter o número correspondente.

        código: http://pastebin.com/Mg8PnVFb

  10. Olá Demonio! No final do codigo não faltou liberar memoria aloca pela função calloc para evitar vazamento de memoria?Ou não precisa mesmo?
    Free(num);

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