Permutar una palabra cualquiera, VF.

Permutar.cpp

#include <bits/stdc++.h>
using namespace std;

// Variables usadas para el tamaño de la palabra [Global]
// y para el numero de permutaciones sin repeticiones existentes
int num_perm;
// Map usado para almacenar las permutaciones
map <string,int> valida;
map <string,int>::iterator it;


void Permutar(string palabra, string permutacion,bool *marcas){
	// En caso de que la permutacion sea del tamaño de la palabra
	if(palabra.length() == permutacion.length()){
		// Metemos la permutacion al map
		valida[permutacion]++; cout << permutacion;
		// Si el map tiene como llave 1, significa que es la primera vez que aparece
		if(valida[permutacion] == 1){
			cout << "<- UNICA :D" << endl;
			num_perm++; //Se cuenta una permutacion
		} // En caso contrario, no es la primera vez
		else cout << "<- REPETIDA :(" << endl;
	}
	// Ciclo para usar TODAS las letras de la palabra
	for(int i=0; i<palabra.length(); i++){
		// Si puedo usarla
		if(!marcas[i]){
			// Digo que la estoy usando
			marcas[i] = true;
			// Creo una permutacion usando lo que traigo, mas lo que acabo de ver
			string a = permutacion;
			a += palabra[i];
			// Llamamos recursivamente a Permutar
			Permutar(palabra, a, marcas);
			// Liberamos la letra en el regreso de la recursion
			marcas[i] = false;
		}
	}
}

int main(){
	string palabra;
	cout << "Mete la palabra: "; cin >> palabra;
	// Una marca para cada letra de la palabra
	bool marcas[palabra.size()];
	num_perm = 0;
	Permutar(palabra,"",marcas);
	cout << "Numero de permutaciones en total: " << num_perm << endl;
	// Ciclo auxiliar para ver el map y sus valores
	cout << "*******************************************" << endl;
	for(it = valida.begin(); it!=valida.end(); it++)
		cout << "La palabra: " << it->first << " se repite -> " << it->second << " veces" << endl;
	return 0;
}