Algorithm to generate all permutation by selecting some or all charaters

Question

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 }.

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.

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.

Thanks, GG

I didn't read your code, but your verbal description sounds correct: use [en.wikipedia.org/wiki/Power_set] together with permutation. To enumerate a power set, think about incrementing a binary number, where each "digit" corresponds to the number of times an input element was selected to appear in the output. For repeated elements in the input set, some "digits" of the "binary" number will become ternary, or the repetition count of that element. — rwong
– rwong, Commented Oct 2, 2010 at 7:13
Note that for a string of length N you'll have 2^N-1 distinct non-empty subsets in the worst case (if all characters are different) and for each subset consisting of L characters, you'll have L! permutations. — Andre Holzner
– Andre Holzner, Commented Oct 2, 2010 at 7:25

score 3 · Accepted Answer · 2010-10-02 07:20:11Z

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

Next_permutation uses a constant size, but you can add a loop to deal with varying size. Or just store in a set to eliminate the extra dupes for you:

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

I'm not able to figure out how to do that, can you elaborate a bit ?
I guess there is some problems here. lets say for string "acbc" your results : 1a2ac3acb4acbc5acc6accb7b8ba9bac10bacc11bc12bca13bcac14bcc15bcca16c17ca18cab19ca bc20cac21cacb22cb23cba24cbac25cbc26cbca27cc28cca29ccab30ccb31ccba but it should be 1a2c3b4ac5ca6ab7ba8bc9cb10cc11bc12cb13abc14acb15bac16bca17cab18cba19acc20cac21cc a22abc23acb24bac25bca26cab27cba28bcc29cbc30ccb31abcc32acbc33accb34bacc35bcac36bc ca37cabc38cacb39cbac40cbca41ccab42ccba
@GG: Ah, I missed it at first: next_permutation requires the initial state to be sorted, if you want to go through all permutations. Use std::sort if necessary.

Nikita Rybak · Accepted Answer · 2010-10-02 07:52:13Z

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.

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

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)

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.

so I can make output size long long, since I'm using it for printing serial number. For int, I can generate combination upto n = 32
@GG Just printing 10^9 different strings should take time close to hour (and about 10GB of disk space). Is it what you want?
@nikita I dont see any other way? Or I should put a restriction that please don't give me a number greater than 9.
@GG There's no way to print 10^9 strings without printing them. (If you change requirements, e.g. if you decide that you only want to know amount of those strings, that would be a different story.) So, my suggestion is to stay with your current program: you won't get much faster solution.

Collectives™ on Stack Overflow

Algorithm to generate all permutation by selecting some or all charaters

2 Answers 2

3 Comments

8 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

8 Comments

Linked

Related