Algoritmos recursivos: permutações

Esta página foi extraída (com algumas modificações) do capítulo 5, seção 5.2, do livro de Eric Roberts. O capítulo ilustra bem o poder da recursão.

Lista de todas as permutações

Quero um programa que imprima todas as permutações dos caracteres de uma cadeia de caracteres. Exemplo: as permutações da cadeia   ABC   são

         ABC
         ACB
         BAC
         BCA
         CAB
         CBA

Eis a solução de Eric Roberts:

#include <string.h> typedef char * string; // Esta função recebe uma cadeia de caracteres str // e imprime todas as permutações dos caracteres // da cadeia. void ListPermutations( string str) { RecursivePermute( str, 0); }

O trabalho pesado é feito pela função "auxiliar" RecursivePermute, que resolve um problema mais geral:

// A função abaixo recebe uma cadeia de caracteres str // e imprime todas permutações de str que começam com // os k primeiros caracteres de str. No fim da execução // da função, a cadeia str é idêntica à original. void RecursivePermute( string str, int k) { int i, len; len = strlen( str); if (k == len) { printf( "%s\n", str); } else { for (i = k; i < len; i++) { ExchangeCharacters( str, k, i); RecursivePermute( str, k + 1); ExchangeCharacters( str, i, k); } } } // A função abaixo troca de posição os caracteres p1 e p2 // da cadeia str. void ExchangeCharacters( string str str[], int p1, int p2) { char tmp; tmp = str[p1]; str[p1] = str[p2]; str[p2] = tmp; }

Exercícios

1. Quantas permutações tem uma cadeia de n caracteres?

2. Se a cadeia de caracteres tiver caracteres repetidos (como "banana"), algumas das permutações serão idênticas a outras. Escreva uma versão da função que imprime todas as permutações sem repetições.

3. Se uma cadeia tem n caracteres, sendo dois iguais a 'a', três iguais a 'b', quatro iguais a 'c', e todos os demais caracteres distintos entre si, qual o número total de permutações distintas?