无需任何循环即可递归生成功率集

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(以便"附加"参数实际上是列表中的第一个元素).