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/