算法选择部分或全部字数生成所有排列 [英] Algorithm to generate all permutation by selecting some or all charaters

问题描述

我需要生成一个字符串的所有排列与选择的一些内容。就像如果我的字符串为abc的输出将是{A，B，C，AB，BA，AC，CA，BC，CB，ABC，ACB，BAC，BCA，CAB，CBA}。

I need to generate all permutation of a string with selecting some of the elements. Like if my string is "abc" output would be { a,b,c,ab,ba,ac,ca,bc,cb,abc,acb,bac,bca,cab,cba }.

我想到了一个基本的算法中，我产生ABC，这是所有可能的组合{A，B，C，AB，AC，BC，ABC}，然后重排所有的人。

I thought a basic algorithm in which I generate all possible combination of "abc" which are {a,b,c,ab,ac,bc,abc} and then permute all of them.

那么，有没有有效的置换算法通过它我可以生成所有可能的排列具有不同的尺寸。

So is there any efficient permutation algorithm by which I can generate all possible permutation with varying size.

在code我写了这是：

The code I wrote for this is :

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

我需要使用哈希避免同样的组合，所以请让我知道，我怎样才能使这个算法比较好。

I need to use a hash for avoiding same combination, so please let me know how can I make this algorithm better.

谢谢， GG

推荐答案

我不认为你可以写更快的程序比你了。主要的问题是输出尺寸：有为了的n * 2 ^ N （子集数*平均数量排列一个子集），这已经是＆GT; 10 ^ 9 为10个不同的字符的字符串。

I don't think you can write much faster program than you have already. The main problem is the output size: it has order of n!*2^n (number of subsets * average number of permutations for one subset), which is already > 10^9 for a string of 10 different characters.

由于STL的 next_permutation 增加了非常有限的复杂性，这样的小弦，你的程序的时间复杂度已经是近 O（输出尺寸）。

Since STL's next_permutation adds very limited complexity for such small strings, your program's time complexity is already nearly O(output size).

但你可以让你的程序有点简单。尤其是，的（K = 1; K＆LT; = N; k ++）循环似乎没有必要：你已经计算的变量子集的大小 C 里面。所以，只要有时int k = C 而不是如果（C == K）。 （你还需要考虑的情况下，空的子集：我== 0 ）

But you can make your program a bit simpler. In particular, for( k =1; k<=n; k++) loop seems unnecessary: you already calculate size of subset in variable c inside. So, just have int k = c instead of if (c == k). (You'll also need to consider case of empty subset: i == 0)

修改
事实上，这里只有9864100的ñ== 10输出（而不是〜10 ^ 9 ）。不过，我的观点是一样的：你的程序已经浪费了唯一的O（next_permutation）时间为每个输出，这是非常，非常小

edit
Actually, there's only 9864100 outputs for n == 10 (not ~ 10^9). Still, my point remains the same: your program already wastes only "O(next_permutation)" time for each output, which is very, very little.

这篇关于算法选择部分或全部字数生成所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！