Algorithme pour générer toutes les permutations en sélectionnant certains ou tous les charaters

Question

Je dois générer toute la permutation d'une chaîne en sélectionnant certains des éléments. Comme si ma chaîne est "abc", la sortie serait {a, b, c, ab, ba, ac, ca, bc, cb, abc, acb, bac, bca, cab, cba}.

Je pensais un algorithme de base dans lequel je génère toutes les combinaisons possibles de "abc" qui sont {a, b, c, ab, ac, bc, abc}, puis les permuter tous.

Y a-t-il donc un algorithme de permutation efficace par lequel je peux générer toutes les permutations possibles avec des tailles variables.

Le code que j'ai écrit pour cela est:

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

je dois utiliser un hachage pour éviter même combinaison, alors s'il vous plaît laissez-moi savoir comment puis-je faire mieux cet algorithme.

Merci, GG

Answer 1

Je ne pense pas que vous pouvez écrire le programme beaucoup plus rapide que vous avez déjà. Le problème principal est la taille de sortie: il a l'ordre de n!*2^n (nombre de sous-ensembles * nombre moyen de permutations pour un sous-ensemble), qui est déjà > 10^9 pour une chaîne de 10 caractères différents.

Depuis next_permutation STL ajoute la complexité très limitée pour ces petites chaînes, complexité du temps de votre programme est déjà presque O(output size). Mais vous pouvez rendre votre programme un peu plus simple. En particulier, for(k =1; k<=n; k++) boucle semble inutile: vous calculez déjà la taille du sous-ensemble dans la variable c à l'intérieur. Donc, il suffit d'avoir int k = c au lieu de if (c == k). (Vous devez également considérer le cas du sous-ensemble vide: i == 0)

modifier
En fait, il n'y a que 9.864.100 sorties pour n == 10 (non ~ 10^9). Pourtant, mon point reste le même: votre programme ne gaspille déjà que le temps "O (next_permutation)" pour chaque sortie, ce qui est très, très peu.

Answer 2

voir cette Algorithm to return all combinations of k elements from n

solutions très détaillées à votre problème

Answer 3

#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 utilise une taille constante, mais vous pouvez ajouter une boucle pour faire face à taille variable. Ou tout simplement stocker dans un ensemble pour éliminer les dupes supplémentaires pour vous:

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