Qual è la soluzione migliore per creare sottoinsiemi di un set di caratteri?
-
09-06-2019 - |
Domanda
So che il "migliore" è soggettivo, quindi secondo te qual è la soluzione migliore per il seguente problema:
Data una stringa di lunghezza n (diciamo "abc"), genera tutti i sottoinsiemi propri della stringa.Quindi, per il nostro esempio, l'output sarebbe {}, {a}, {b}, {c}, {ab}, {bc}, {ac}.{abc}.
Cosa ne pensi?
Soluzione
Vuoi il insieme di potenza.Può essere calcolato ricorsivamente e induttivamente. ;-)
Altri suggerimenti
L'approccio ricorsivo: i sottoinsiemi di "abc" sono di due tipi:quelli che sono sottoinsiemi di "bc", e quelli che sono "a" più un sottoinsieme di "bc".Quindi se conosci i sottoinsiemi di "bc", è facile.
In alternativa, una stringa di lunghezza n ha 2^n sottoinsiemi.Quindi scrivi due cicli nidificati:i conta da 0 a 2^n -1 (per i sottoinsiemi) e j conta da 0 a n-1 (per i caratteri nell'iesimo sottoinsieme).Visualizza il jesimo carattere della stringa se e solo se il jesimo bit di i è 1.
(Beh, hai detto che il "migliore" era soggettivo...)
Interpretare un numero in rappresentazione binaria come indicante quali elementi sono inclusi nel sottoinsieme.Supponiamo che tu abbia 3 elementi nel tuo set.Il numero 4 corrisponde a 0100 in notazione binaria, quindi lo interpreterai come un sottoinsieme di dimensione 1 che include solo il 2° elemento.In questo modo, generare tutti i sottoinsiemi conta fino a (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;
}
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")
Scusate lo pseudocodice...
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++;
}
//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;
}