java - 从常规方法创建递归方法

Question

我下面的代码完全符合我希望程序执行的操作。唯一的问题是我什至不知道从哪里开始使方法递归。我理解使用递归来解决阶乘和其他问题，但这个问题有点超出我的理解范围。谁能帮我指出正确的方向？

import java.util.LinkedHashSet;

public class Power_Set{
  public static void main(String[] args) {
    //construct the set S = {a,b,c}
    String set[] = {"a", "b", "c"};

    //form the power set
    LinkedHashSet myPowerSet = powerset(set);

    //display the power set
    System.out.println(myPowerSet.toString());
  }

  /**
   * Returns the power set from the given set by using a binary counter
   * Example: S = {a,b,c}
   * P(S) = {[], [c], [b], [b, c], [a], [a, c], [a, b], [a, b, c]}
   * @param set String[]
   * @return LinkedHashSet
   */
  private static LinkedHashSet powerset(String[] set) {
    //create the empty power set
    LinkedHashSet power = new LinkedHashSet();

    //get the number of elements in the set
    int elements = set.length;

    //the number of members of a power set is 2^n
    int powerElements = (int) Math.pow(2,elements);

    //run a binary counter for the number of power elements
    for (int i = 0; i < powerElements; i++) {        
      //convert the binary number to a string containing n digits
      String binary = intToBinary(i, elements);

      //create a new set
      LinkedHashSet innerSet = new LinkedHashSet();

      //convert each digit in the current binary number to the corresponding     element
      //in the given set
      for (int j = 0; j < binary.length(); j++) {
        if (binary.charAt(j) == '1')
          innerSet.add(set[j]);
        }

        //add the new set to the power set
        power.add(innerSet);
      }

      return power;
    }

    /**
     * Converts the given integer to a String representing a binary number
     * with the specified number of digits
     * For example when using 4 digits the binary 1 is 0001
     * @param binary int
     * @param digits int
     * @return String
     */
    private static String intToBinary(int binary, int digits) {
      String temp = Integer.toBinaryString(binary);
      int foundDigits = temp.length();
      String returner = temp;
      for (int i = foundDigits; i < digits; i++) {
        returner = "0" + returner;
      }
      return returner;
    }
 }

Answer 1

首先，我们来了解一下什么是幂集。根据wikipedia :

A power set ... is the set of all subsets of S, including the empty set and S itself.

对于递归，我们关心两件事:“基本情况”和“N+1 情况”。对于幂集，基本情况是包含空集的集合:

f({}) => {{}} 

N+1 情况假设您已经拥有 N (f(N)) 的幂集，并且仅查看该幂集与向 N 添加单个元素的幂集之间的差异。这是为什么重要的？嗯，因为递归背后的想法是解决逐渐简单的问题，直到达到基本情况。对于基本情况以上的每个 n，此步骤都是相同的:

f({a}) => {{a},{}}
  + b  => {{a,b}, {a}, {b}, {}}

那么这两组有什么区别呢？好吧，对于原始集合中的每个元素，我们都获取该元素并将 b 添加到该元素。 (注意，这里的每个“元素”都是一个集合。)

让我们用伪代码来做到这一点:

 function addElement(someSet, newElement)
   for each element in someSet              // {a} and {} in the example
     add newElement to that set             // should return {{a,b},{b}}
   take the new set of sets and add someSet // add in {a} and {} (someSet, the original set)

编写完整函数现在只需为原始集合中的每个成员调用此函数即可。这就是您的基础案例和 N+1 案例的用武之地:

 function powerSet(originalSet)
   if originalSet is empty, return a set of the empty set  // {{}}  (VERY important it is a set of sets!)
   else
     get the powerSet of the originalSet minus one element //this is the recursive call
     call addElement on that result and the element you took away
     return this result

我将其转换为代码留给您，但这应该非常简单。