java - 递归地生成功率集，没有任何循环

Question

如何编写递归方法 PowerSet(String input) 来打印出传递给它的字符串的所有可能组合？

例如:PowerSet("abc") 会打印出abc, ab, ac, bc, a, b, c

我见过一些带有循环的递归解决方案，但在这种情况下不允许使用循环。

有什么想法吗？

编辑:所需方法只有一个参数，即字符串输入。

Answer 1

abcd 的幂集是 abc, abd, acd 的幂集的并集 (加上集合 abcd 本身*)。

 P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`)

_{* 注意 空集，它是 P(abcd) 的成员，也是 P(abc)、P(abd) 的成员，...所以等价上述内容成立。}

递归地，P(abc) = {abc} + P(ab) + P(ac ), 等等

第一种方法，在伪代码中，可以是:

powerset(string) {
  add string to set;
  for each char in string {
   let substring = string excluding char,
   add powerset(substring) to set
  }
  return set;      
}

递归在字符串为空时结束(因为它永远不会进入循环)。

如果您真的想要没有 循环，则必须将该循环转换为另一个递归。 现在我们要从abc

生成ab、ac和cb

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
}

另一种方法 实现一个递归函数 P，它要么从其参数中删除第一个字符，要么不删除。 (这里+表示并集，.表示拼接，λ为空串)

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

然后

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 

如果允许循环，则 P 是幂集函数。否则，我们将需要一个单参数无循环函数来将给定字符连接到给定字符串集(这显然是两个事物)。

可以通过使用 String.replace 进行一些调整(如果需要 String 结果，或者将 Set 替换为 List(因此“附加”参数实际上是列表中的第一个元素)。