Quelle est la meilleure solution pour créer des sous-ensembles d'un ensemble de caractères?

Question

Je sais que le 'meilleur' ​​est subjectif, donc selon vous, quelle est la meilleure solution pour le problème suivant:

Étant donné une chaîne de longueur n (disons "abc"), générez tous les sous-ensembles propres de la chaîne. Donc, pour notre exemple, la sortie serait {}, {a}, {b}, {c}, {ab}, {bc}, {ac}. {abc}.

Qu'en pensez-vous?

Answer 1

Vous souhaitez le power set. Il peut être calculé recursively and inductively. ;-)

Answer 2

def subsets(s): 
    r = [] 
    a = [False] * len(s) 
    while True: 
     r.append("".join([s[i] for i in range(len(s)) if a[i]])) 
     j = 0 
     while a[j]: 
      a[j] = False 
      j += 1 
      if j >= len(s): 
       return r 
     a[j] = True 

print subsets("abc") 

Answer 3

Pardon code pseudo ...

int i = 0; 
Results.push({}); 

While(i > Inset.Length) { 
    Foreach(Set s in Results) { 
    If(s.Length == i) { 
     Foreach(character c in inSet) 
      Results.push(s+c); 
    } 
    i++; 
} 

Answer 4

L'approche récurrente - les sous-ensembles de "abc" sont disponibles en deux types: ceux qui sont des sous-ensembles de "bc", et ceux qui sont "a" plus un sous-ensemble de "bc". Donc, si vous connaissez les sous-ensembles de "bc", c'est facile.

En variante, une chaîne de longueur n a 2^n sous-ensembles. Donc écrivez deux boucles imbriquées: je compte de 0 à 2^n -1 (pour les sous-ensembles), et j compte de 0 à n-1 (pour les caractères du sous-ensemble ith). Sortie le caractère de la chaîne jème si et seulement si le bit i est jème 1.

(Eh bien, vous avez dit que « meilleur » est subjective ...)

Answer 5

Interpréter un certain nombre dans la représentation binaire indiquant quels éléments sont inclus dans le sous-ensemble. Supposons que vous avez 3 éléments dans votre ensemble. Le numéro 4 correspond à 0100 en notation binaire, donc vous l'interpréterez comme un sous-ensemble de taille 1 qui ne comprend que le 2e élément. De cette façon, générer tous les sous-compte est à (2^n) -1

char str [] = "abc"; 
    int n = strlen(str); // n is number of elements in your set 

    for(int i=0; i< (1 << n); i++) { // (1 << n) is equal to 2^n 
     for(int j=0; j<n; j++) { // For each element in the set 
      if((i & (1 << j)) > 0) { // Check if it's included in this subset. (1 << j) sets the jth bit 
       cout << str[j]; 
      } 
     } 
     cout << endl; 
    } 

Answer 6

//recursive solution in C++ 
set<string> power_set_recursive(string input_str) 
{ 
    set<string> res; 
    if(input_str.size()==0) { 
     res.insert(""); 
    } else if(input_str.size()==1) { 
     res.insert(input_str.substr(0,1)); 
    } else { 
     for(int i=0;i<input_str.size();i++) { 
      set<string> left_set=power_set_iterative(input_str.substr(0,i)); 
      set<string> right_set=power_set_iterative(input_str.substr(i,input_str.size()-i)); 
      for(set<string>::iterator it1=left_set.begin();it1!=left_set.end();it1++) { 
       for(set<string>::iterator it2=right_set.begin();it2!=right_set.end();it2++) { 
        string tmp=(*it1)+(*it2); 
        sort(tmp.begin(),tmp.end()); 
        res.insert(tmp); 
       } 
      } 
     } 
    } 
    return res; 
} 


//iterative solution in C++ 
set<string> power_set_iterative(string input_str) 
{ 
    set<string> res; 
    set<string> out_res; 
    res.insert(""); 
    set<string>::iterator res_it; 
    for(int i=0;i<input_str.size();i++){ 
     for(res_it=res.begin();res_it!=res.end();res_it++){ 
       string tmp=*res_it+input_str.substr(i,1); 
       sort(tmp.begin(),tmp.end()); 
       out_res.insert(tmp); 
     } 
     res.insert(input_str.substr(i,1)); 
     for(set<string>::iterator res_it2=out_res.begin();res_it2!=out_res.end();res_it2++){ 
      res.insert(*res_it2); 
    } 
    out_res.clear(); 
    } 
    return res; 
}