Bir dizi karakterin alt kümelerini oluşturmak için en iyi çözüm hangisi?

Question

'En iyisi' subjektiftir, bu yüzden size göre, aşağıdaki sorun için en iyi çözüm nedir:

Bir uzunluk dizesi verildiğinde ("abc"), dizenin tüm uygun alt kümelerini oluşturun. Dolayısıyla, örneğimiz için çıktı {}, {a}, {b}, {c}, {ab}, {bc}, {ac} olacaktır. {ABC}.

Ne düşünüyorsunuz?

Answer 1

power set. recursively and inductively hesaplanabilir. ;-)

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 sahte kod ...

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

özyinelemeli yaklaşım - "abc" alt kümeleri iki türü vardır: "bc" alt kümeleri olan olanlar ve olanlar "a" artı "bc" nin bir alt kümesi. Yani "bc" alt kümelerini biliyorsanız, bu kolaydır. Alternatif olarak, bir uzunluk dizisi n 2^n alt kümesine sahiptir. Yani iki iç içe döngüleri yazın: 0'dan 2^n -1'e (altkümeler için) sayar ve j 0'dan n-1'e (ith alt kümesindeki karakterler için) sayar. dizesinin j karakter ve i j nci biraz yalnızca 1.

(Eh, sübjektif "en iyi" olduğunu dediniz ...) eğer Çıktı

Answer 5

olarak ikili gösteriminde bir numara yorumlayın Alt kümeye hangi öğelerin dahil edildiğini gösterir. Setinizde 3 elementiniz olduğunu varsayalım. Sayı 4, ikili gösterimde 0100'e karşılık gelir, böylece bunu yalnızca 2. elemanı içeren bir boyut 1 alt kümesi olarak yorumlayacaksınız. Bu şekilde, tüm alt küme işlemleri (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; 
} 

kadar saymaya devam eder