문자 집합의 하위 집합을 만드는 데 가장 좋은 솔루션은 무엇입니까?

Question

'best'는 주관적이므로 다음 문제에 대한 최선의 해결책은 무엇입니까?

길이가 n 인 문자열 (예 : "abc")이 있으면 문자열의 모든 적절한 하위 집합을 생성하십시오. 예를 들어, 출력은 {}, {a}, {b}, {c}, {ab}, {bc}, {ac}입니다. {알파벳}.

당신은 어떻게 생각하십니까?

Answer 1

power set을 원합니다. 그것은 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

용서는 의사 코드는 ...

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

재귀 적 접근 - "ABC"의 하위 집합이 두 가지 유형에 와서 : "BC"의 부분 집합 인 것들, 그리고있는 그 "a"와 "bc"의 하위 집합. 따라서 "bc"의 하위 집합을 알고 있다면 쉽습니다.

또는 길이가 n 인 문자열에는 2^n 개의 하위 집합이 있습니다. 그래서 두 개의 중첩 된 루프를 작성합니다. i는 0에서 2^n-1 (부분 집합의 경우)을 계산하고 j는 0부터 n-1까지 (i 번째 하위 집합의 문자의 경우) 계산합니다. 문자열의 j 번째 문자와 나는의 j 번째 비트 인 경우에만 1

(글쎄, 당신은 주관적 "최고"라고 말 했는가 ...) 경우 출력

Answer 5

은 이진 표현에 숫자를 해석 부분 집합에 포함 된 요소를 나타냅니다. 세트에 3 가지 요소가 있다고 가정 해 봅시다. 숫자 4는 이진 표기법에서 0100에 해당하므로이 값을 두 번째 요소 만 포함하는 크기 1의 하위 집합으로 해석합니다. 이 방법은 모든 서브 세트를 생성하는 단계 (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; 
} 

까지 세고