Algoritmo para generar toda la permutación seleccionando algunos o todos los personajes
Necesito generar toda la permutación de una cadena con la selección de algunos de los elementos. Como si mi cadena es "abc", la salida sería {a, b, c, ab, ba, ac, ca, bc, cb, abc, acb, bac, bca, cab, cba}.
Pensé en un algoritmo básico en el que genero todas las combinaciones posibles de "abc" que son {a, b, c, ab, ac, bc, abc} y luego las permuto a todas.
Entonces, ¿hay algún algoritmo de permutación eficiente mediante el cual pueda generar toda la permutación posible con un tamaño variable.
El código que escribí para esto es:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;
int permuteCount = 1;
int compare (const void * a, const void * b)
{
return ( *(char*)a - *(char*)b);
}
void permute(char *str, int start, int end)
{
// cout<<"before sort : "<<str;
// cout<<"after sort : "<<str;
do
{
cout<<permuteCount<<")"<<str<<endl;
permuteCount++;
}while( next_permutation(str+start,str+end) );
}
void generateAllCombinations( char* str)
{
int n, k, i, j, c;
n = strlen(str);
map<string,int> combinationMap;
for( k =1; k<=n; k++)
{
char tempStr[20];
int index =0;
for (i=0; i<(1<<n); i++) {
index =0;
for (j=0,c=0; j<32; j++) if (i & (1<<j)) c++;
if (c == k) {
for (j=0;j<32; j++)
if (i & (1<<j))
tempStr[ index++] = str[j];
tempStr[index] = '\0';
qsort (tempStr, index, sizeof(char), compare);
if( combinationMap.find(tempStr) == combinationMap.end() )
{
// cout<<"comb : "<<tempStr<<endl;
//cout<<"unique comb : \n";
combinationMap[tempStr] = 1;
permute(tempStr,0,k);
} /*
else
{
cout<<"duplicated comb : "<<tempStr<<endl;
}*/
}
}
}
}
int main () {
char str[20];
cin>>str;
generateAllCombinations(str);
cin>>str;
}
Necesito usar un hash para evitar la misma combinación, así que avíseme cómo puedo mejorar este algoritmo.
Gracias GG