Ich muss alle Permutationen eines Strings mit der Auswahl einiger Elemente erzeugen. Als ob meine Zeichenkette "abc" wäre, wäre die Ausgabe {a, b, c, ab, ba, ac, ca, bc, cb, abc, acb, bac, bca, cab, cba}.

Ich dachte an einen grundlegenden Algorithmus, in dem ich alle möglichen Kombinationen von "abc" (a, b, c, ab, ac, bc, abc) generiere und dann alle permutiere.

So gibt es einen effizienten Permutationsalgorithmus, mit dem ich alle möglichen Permutationen mit unterschiedlicher Größe erzeugen kann.

Der Code, den ich dafür geschrieben habe, ist:

    #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;
    }

Ich muss einen Hash verwenden, um die gleiche Kombination zu vermeiden. Bitte lassen Sie mich wissen, wie ich diesen Algorithmus verbessern kann.

Danke, GG