Home | Administração | Fórum | Livros | WWW | Diário | Tarefas | Alunos |
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.
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; }