代码之家 › 专栏 › 技术社区 › GG.

通过选择部分或全部特征生成所有排列的算法

combinations permutation algorithm c++

GG. · 技术社区 · 15 年前

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

我想到了一个基本的算法,在这个算法中,我生成了所有可能的“a b c”的组合,它们是a、b、c、ab、ac、bc、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

3 回复 | 直到 15 年前

Nikita Rybak 15 年前

我认为你写程序的速度不能比现在快得多。主要问题是输出大小:它的顺序是 n!*2^n (子集数*一个子集的平均排列数),已经 > 10^9 10个不同字符的字符串。

从STL开始 next_permutation 为如此小的字符串添加非常有限的复杂性,您的程序的时间复杂性已经接近 O(output size) .

但是你可以让你的程序简单一点。特别地, for( k =1; k<=n; k++) 循环似乎不必要:您已经计算了变量中子集的大小 c 在里面。所以,只要 int k = c 而不是 if (c == k) . (您还需要考虑空子集的情况: i == 0 )

编辑
实际上,只有9864100个输出用于 n == 10 (不是) ~ 10^9 )不过,我的观点仍然是一样的:您的程序对每个输出只浪费“O(下一个排列)”时间,这非常非常少。

Roger Pate 15 年前

#include <algorithm>
#include <iostream>
#include <string>

int main() {
  using namespace std;
  string s = "abc";
  do {
    cout << s << '\n'; 
  } while (next_permutation(s.begin(), s.end()));
  return 0;
}

下一个排列使用一个常量大小,但是您可以添加一个循环来处理不同的大小。或者将其储存在一个集合中,以消除多余的重复:

#include <set>

int main() {
  using namespace std;
  string s = "abc";
  set<string> results;
  do {
    for (int n = 1; n <= s.size(); ++n) {
      results.insert(s.substr(0, n));
    }
  } while (next_permutation(s.begin(), s.end()));
  for (set<string>::const_iterator x = results.begin(); x != results.end(); ++x) {
    cout << *x << '\n';
  }
  return 0;
}

Community CDub 8 年前

看看这个 Algorithm to return all combinations of k elements from n

非常详细的问题解决方案