3

そのため、特定の N 要素セットからすべての k 要素サブセットを見つけようとするこの問題に悩まされています。式 C(n,k)=C(n-1, k-1)+C(n-1, k) を使用して k-subset の総数を知っており、それを行う方法も考えています繰り返しますが、再帰的な解決策を考えようとすると行き詰まります。誰でも私にヒントを与えることができますか？ありがとう！

4

3 に答える 3

6

セットの各要素について、その要素を取得し、残りの N-1 要素セットのすべての (k-1) サブセットを順番に追加します。

「それは暗く嵐の夜だった、そして船長は言った...」

于 2010-11-04T15:31:15.313 に答える
1

より良い

k=0これは、空のセットを含むセットを返すと思われるため、このケースでは壊れていますが、これは正しくありません。ともかく。ここにも繰り返しがあります。目標が純粋に再帰的である場合は、おそらくそれを再帰に置き換えることができます。これは、 wikipedia: powersetで提供されているアルゴリズムをかなり単純に変更したものです。コーナー ケース (k=0) の修正は読者に任せます。

これは適切な末尾再帰ではなく、ほとんどの JVM で問題になるわけではありません。（IBM JVMがこれを行うと思います...）

class RecursivePowerKSet
{  
  static public <E> Set<Set<E>> computeKPowerSet(final Set<E> source, final int k)
  {
    if (k==0 || source.size() < k) {
      Set<Set<E>> set = new HashSet<Set<E>>();
      set.add(Collections.EMPTY_SET);
      return set;
    }

    if (source.size() == k) {
      Set<Set<E>> set = new HashSet<Set<E>>();
      set.add(source);
      return set;
    }

    Set<Set<E>> toReturn = new HashSet<Set<E>>();

    // distinguish an element
    for(E element : source) {
      // compute source - element
      Set<E> relativeComplement = new HashSet<E>(source);
      relativeComplement.remove(element);

      // add the powerset of the complement
      Set<Set<E>> completementPowerSet = computeKPowerSet(relativeComplement,k-1);
      toReturn.addAll(withElement(completementPowerSet,element));
    }

    return toReturn;
  }

  /** Given a set of sets S_i and element k, return the set of sets {S_i U {k}} */ 
  static private <E> Set<Set<E>> withElement(final Set<Set<E>> source, E element)
  {

    Set<Set<E>> toReturn = new HashSet<Set<E>>();
    for (Set<E> setElement : source) {
      Set<E> withElementSet = new HashSet<E>(setElement);
      withElementSet.add(element);
      toReturn.add(withElementSet);
    }

    return toReturn;
  }

  public static void main(String[] args)
  {
    Set<String> source = new HashSet<String>();
    source.add("one");
    source.add("two");
    source.add("three");
    source.add("four");
    source.add("five");

    Set<Set<String>> powerset = computeKPowerSet(source,3);

    for (Set<String> set : powerset) {
      for (String item : set) {
        System.out.print(item+" ");
      }
      System.out.println();
    }   
  }
}

Power Set Only これはおそらく十分に到達できず、実際にはエレガントではありませんが、完全な powerset を再帰的に計算し、(反復して) サイズを調整します。

class RecursivePowerSet
{


  static public <E> Set<Set<E>> computeConstrainedSets(final Set<Set<E>> source, final SizeConstraint<Set<E>> constraint)
  {
    Set<Set<E>> constrained = new HashSet<Set<E>>();
    for (Set<E> candidate : source) {
      if (constraint.meetsConstraint(candidate)) {
        constrained.add(candidate);
      }
    }
    return constrained;
  }

  static public <E> Set<Set<E>> computePowerSet(final Set<E> source)
  {

    if (source.isEmpty()) {
      Set<Set<E>> setOfEmptySet = new HashSet<Set<E>>();
      setOfEmptySet.add(Collections.EMPTY_SET);
      return setOfEmptySet;
    }


    Set<Set<E>> toReturn = new HashSet<Set<E>>();

    // distinguish an element
    E element = source.iterator().next();

    // compute source - element
    Set<E> relativeComplement = new HashSet<E>(source);
    relativeComplement.remove(element);

    // add the powerset of the complement
    Set<Set<E>> completementPowerSet = computePowerSet(relativeComplement);
    toReturn.addAll(completementPowerSet);
    toReturn.addAll(withElement(completementPowerSet,element));

    return toReturn;
  }

  static private <E> Set<Set<E>> withElement(final Set<Set<E>> source, E element)
  {

    Set<Set<E>> toReturn = new HashSet<Set<E>>();
    for (Set<E> setElement : source) {
      Set<E> withElementSet = new HashSet<E>(setElement);
      withElementSet.add(element);
      toReturn.add(withElementSet);
    }

    return toReturn;
  }

  public static void main(String[] args)
  {
    Set<String> source = new HashSet<String>();
    source.add("one");
    source.add("two");
    source.add("three");
    source.add("four");
    source.add("five");

    SizeConstraint<Set<String>> constraint = new SizeConstraint<Set<String>>(3);

    Set<Set<String>> powerset = computePowerSet(source);
    Set<Set<String>> constrained = computeConstrainedSets(powerset, constraint);
    for (Set<String> set : constrained) {
      for (String item : set) {
        System.out.print(item+" ");
      }
      System.out.println();
    }

  }

  static class SizeConstraint<V extends Set> {

    final int size;
    public SizeConstraint(final int size)
    {
     this.size = size; 
    }

    public boolean meetsConstraint(V set)
    {
      return set.size() == size;
    }
  }

}
于 2010-11-04T16:30:35.923 に答える
0

ここにいくつかの擬似コードがあります。呼び出し値が既に存在するかどうかを確認する再帰呼び出しの前に、各呼び出しの値を保存することで、同じ再帰呼び出しをカットできます。

次のアルゴリズムには、空のセットを除くすべてのサブセットが含まれます。

list * subsets(string s, list * v){
    if(s.length() == 1){
        list.add(s);    
        return v;
    }
    else
    {
        list * temp = subsets(s[1 to length-1], v);     
        int length = temp->size();

        for(int i=0;i<length;i++){
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}
于 2013-02-16T02:03:17.910 に答える