Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
196 views
in Technique[技术] by (71.8m points)

java - Generating power set recursively without any loops

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

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.

Any ideas?

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

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...