La powerset del abcd
è l'unione dei power-set di abc
, abd
, acd
(più set abcd
stessa *).
P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`)
* Si noti che l'insieme vuoto , che è un membro di P (abcd) è anche un membro di P (abc), P (abd), ... così l'equivalenza sopra indicato tiene .
ricorsivo, P (abc
) = {abc
} + P (ab
) + P (ac
), e così via
Un primo approccio, in pseudocodice, potrebbe essere:
powerset(string) {
add string to set;
for each char in string {
let substring = string excluding char,
add powerset(substring) to set
}
return set;
}
La ricorsione termina quando la stringa è vuota (perché non entra mai nel ciclo).
Se si desidera realmente i loop no, sarà necessario convertirlo in un'altra ricorsione. Ora vogliamo generare ab
, ac
e cb
da abc
powerset(string) {
add string to set;
add powerset2(string,0) to set;
return set
}
powerset2(string,pos) {
if pos<length(string) then
let substring = (string excluding the char at pos)
add powerset(substring) to set
add powerset2(string,pos+1) to set
else
add "" to set
endif
return set
}
Un altro approccio implementare una funzione ricorsiva P
che o rimuove il primo carattere da suo argomento, o non lo fa. (Qui +
significa insieme unione, .
significa concatenazione e λ
è la stringa vuota)
P(abcd) = P(bcd) + a.P(bcd)
P(bcd) = P(cd) + b.P(cd)
P(cd) = P(d) + c.P(d)
P(d) = λ+d //particular case
Poi
P(d) = λ+d
R(cd) = P(d) + c.P(d) = λ + d + c.(λ+d) = λ + d + c + cd
R(bcd) = P(cd) + b.P(cd) = λ + d + c + cd + b.(λ + d + c + cd)
= λ + d + c + cd + b + bd + bc + bcd
P(abcd) = λ + d + c + cd + b + bd + bc + bcd
+ aλ + ad + ac + acd + ab + abd + abc + abcd
Se cicli sono stati ammessi, quindi P
è fuori funzione power-impostata. In caso contrario, avremmo bisogno di una funzione loopless a un parametro per concatenare un determinato carattere a un determinato set di stringhe (che ovviamente sono due elementi).
Alcuni aggiustamento potrebbe essere possibile giocando con String.replace
(se un risultato String
è desiderato, o sostituendo Set
con List
(in modo che il parametro "supplementare" è in realtà il primo elemento della lista).
questo caso? quale caso? – SudoRahul
Penso che ci siano ** alcuni ** algoritmi là fuori che possono risolvere questo problema, nel caso tu voglia usare Google per trovarne uno. – Matten
E quasi ogni ciclo può essere sostituito da una funzione ricorsiva. – Matten