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

Question

如何编写一个递归方法PowerSet（字符串输入），该方法打印出传递给它的字符串的所有可能组合？

例如：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;      
}

当字符串为空时，递归结束（因为它从不进入循环）。

如果你真的想 不 循环，你将不得不到循环转换为另一种递归。现在，我们要生成ab，ac并cb从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
}

另一种方法 实现了一个递归函数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使“其他”参数实际上是列表中的第一个元素）。