c++ - 通过选择部分或全部字符来生成所有排列的算法

我需要通过选择一些元素来生成字符串的所有排列。就像我的字符串是“abc”一样，输出将是{a，b，c，ab，ba，ac，ca，bc，cb，abc，acb，bac，bca，cab，cba}。

我以为是一种基本算法，可以生成{a，b，c，ab，ac，bc，abc}的所有“abc”组合，然后对它们进行置换。

因此，有没有一种有效的置换算法，通过它我可以生成大小可变的所有可能置换。

我为此编写的代码是:

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

我需要使用散列来避免相同的组合，因此请让我知道如何使该算法更好。

谢谢，
GG

最佳答案

我不认为您可以编写比现在更快的程序。主要问题是输出大小:它的顺序为n!*2^n(子集数*一个子集的平均排列数)，对于10个不同字符的字符串而言，它已经是> 10^9。

由于STL的next_permutation为这样的小字符串增加了非常有限的复杂度，因此程序的时间复杂度已经接近O(output size)。

但是您可以使程序更简单。尤其是for( k =1; k<=n; k++)循环似乎是不必要的:您已经在其中的c变量中计算了子集的大小。因此，只需使用int k = c而不是if (c == k)即可。 (您还需要考虑空子集的情况:i == 0)

编辑
实际上，n == 10(不是~ 10^9)只有9864100输出。尽管如此，我的观点仍然是不变的:您的程序已经为每个输出仅浪费了“O(next_permutation)”时间，这非常少。