无需任何循环即可递归生成功率集 [英] Generating power set recursively without any loops

问题描述

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

How do you write a recursive method PowerSet(String input) that prints out all possible combinations of a string that is passed to it?

例如：PowerSet（ abc）将打印出abc，ab，ac，bc，a，b，c

For example: PowerSet("abc") will print out abc, ab, ac, bc, a, b, c

我看过一些带循环的递归解决方案，但在这种情况下没有循环被允许。

I have seen some recursive solutions with loops, but in this case no loops are allowed.

任何想法？

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

The required method has only one parameter, i.e. String input.

推荐答案

abcd 的powerset是<$的幂集的并集c $ c> abc ， abd ， acd （加上 abcd 本身*）。

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`)

_{*请注意，空集是P（abcd）的成员，也是P（abc），P（abd），...的成员。所以上述等价值成立。}

_{* 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.}

递归地，P（ abc ）= { abc } + P（ ab ）+ P（ ac ），

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).

如果您真的想要没有循环，则必须将该循环转换为另一个递归。
现在我们要生成 ab ， ac 和 cb 来自 abc

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
}

另一种方法实现递归函数 P 可以从参数中删除第一个字符，也可以不删除。 （此处 + 表示设置union，。表示连接，λ是空字符串）

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

然后

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 就会失效 - 设置功能。否则，我们需要一个单参数无循环函数来将给定字符连接到给定的字符串集（显然是两个事物）。

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).

通过玩 String.replace 可以实现一些调整（如果 String 需要结果，或者用 List 替换 Set （以便附加参数实际上是列表中的第一个元素。）

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).

这篇关于无需任何循环即可递归生成功率集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！