Что не является лучшим решением для создания подмножеств набора символов?

Question

Я знаю, что «лучшее» - это субъективно, поэтому, по вашему мнению, как лучше всего решить следующую проблему:

Учитывая строку длины n (скажем, «abc»), сгенерируйте все правильные подмножества строки. Таким образом, для нашего примера выходные данные будут {}, {a}, {b}, {c}, {ab}, {bc}, {ac}. {} А.

Что ты думаешь?

Answer 1

Вы хотите блок питания . Его можно вычислить рекурсивно и индуктивно . ; -)

Answer 2

Рекурсивный подход - подмножества "abc" бывают двух типов: те, которые являются подмножествами "bc", и те, которые являются "a" плюс подмножество "bc". Так что если вы знаете подмножества "bc", это просто.

В качестве альтернативы, строка длиной n имеет 2 ^ n подмножеств. Итак, напишите два вложенных цикла: i считает от 0 до 2 ^ n -1 (для подмножеств), а j считает от 0 до n-1 (для символов в i-м подмножестве). Выведите j-й символ строки, если и только если j-й бит i равен 1.

(Ну, вы же сказали, что "лучший" был субъективным ...)

Answer 3

Интерпретировать число в двоичном представлении как указывающее, какие элементы включены в подмножество. Давайте предположим, что у вас есть 3 элемента в вашем наборе. Число 4 соответствует 0100 в двоичной записи, поэтому вы будете интерпретировать это как подмножество размера 1, которое включает только 2-й элемент. Таким образом, при генерации всех подмножеств считается до (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 4

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

Answer 5

Простите за псевдокод ...

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 6

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")