The powerset of abcd
is the union of the power-sets of abc
, abd
, acd
(plus the set abcd
itself*).
P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`)
* Note that the empty set, which is a member of P(abcd) is also a member of P(abc), P(abd), ... so the equivalence stated above holds.
Recursively, P(abc
) = {abc
} + P(ab
) + P(ac
), and so on
A first approach, in pseudocode, could be:
powerset(string) {
add string to set;
for each char in string {
let substring = string excluding char,
add powerset(substring) to set
}
return set;
}
The recursion ends when the string is empty (because it never enters the loop).
If your really want no loops, you will have to convert that loop to another recursion.
Now we want to generate ab
, ac
and cb
from 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
}
Another approach implement a recursive function P
that either removes the first character from its argument, or does not. (Here +
means set union, .
means concatenation and λ
is the empty string)
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
Then
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
If loops were allowed, then P
is out power-set function. Otherwise, we would need a one-parameter loopless function for concatenating a given character to a given set of strings (which obviously are two things).
Some tweak could be possible by playing with String.replace
(if a String
result is desired, or by replacing Set
with List
(so that the "additional" parameter is actually the first element in the list).