0

プログラムに実行させたいことを正確に実行するコードを以下に示します。唯一の問題は、メソッドを再帰的にするためにどこから始めればよいかさえわからないことです。階乗やその他の問題に再帰を使用することは理解していますが、これは少し頭を悩ませています。誰かが私を正しい方向に向けるのを手伝ってくれますか?

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 ケース」の 2 つを考慮します。パワー セットに関しては、ベース ケースは空のセットを含むセットです。

f({}) => {{}}

N+1 の場合は、すでに N のベキ集合 (f(N)) を持っていることを前提としており、単にそのベキ集合と N に 1 つの要素を追加したものの違いを調べているだけです。なぜこれが重要なのですか? 再帰の背後にある考え方は、基本ケースに到達するまで、徐々に単純な問題を解決することです。このステップは、基本ケースより上の n ごとに同じになります。

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

では、これら2つのセットの違いは何ですか? 元のセットの各要素について、その要素を取得し、その要素に 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 に答える