0

I have code below that does exactly what I want the program to do. The only problem is I don't even know where to get started to make the methods recursive. I understand using recursion for factorials and other problems but this one is over my head a bit. Can anyone help point me in the right direction?

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;
    }
 }
4

1 回答 1

0

首先，让我们了解一下什么是电源组。根据维基百科：

幂集...是 S 的所有子集的集合，包括空集和 S 本身。

使用递归，我们关心两件事：“基本情况”和“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

我把它转换成代码留给你，但它应该很简单。

于 2013-11-14T00:09:13.690 回答