代码之家  ›  专栏  ›  技术社区  ›  Vaibhav

创建一组字符子集的最佳解决方案是什么?

  •  2
  • Vaibhav  · 技术社区  · 16 年前

    我知道“最佳”是主观的,因此根据您的说法,以下问题的最佳解决方案是什么:

    给定长度为n的字符串(如“abc”),生成该字符串的所有适当子集。因此,对于我们的示例,输出将是{}、{a}、{b}、{c}、{ab}、{bc}、{ac}。{abc}。

    你怎么认为?

    6 回复  |  直到 13 年前
        1
  •  5
  •   Konrad Rudolph    16 年前

    你想要 power set . 这是可以计算出来的 recursively and inductively . ;-)

        2
  •  2
  •   Matt Bishop    16 年前

    或者,长度为n的字符串有2^n个子集。所以写两个嵌套循环:i从0计数到2^n-1(对于子集),j从0计数到n-1(对于第i个子集中的字符)。当且仅当i的第j位为1时,输出字符串的第j个字符。

    (嗯,你确实说过“最好”是主观的…)

        3
  •  1
  •   Sarp Centel    16 年前

        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;
        }
    
        4
  •  0
  •   Greg Hewgill    16 年前
    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")
    
        5
  •  0
  •   Tnilsson    16 年前

    请原谅伪代码。。。

    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++;
    }
    
        6
  •  0
  •   feliciafay    11 年前
    //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;
    }