如何在Java中使用递归生成一个包含N个元素的集合的所有k个元素的子集

Question

我现在遇到了一个问题，需要从给定的N元素集合中找到所有的k元素子集。我知道使用公式C(n,k)=C(n-1, k-1)+C(n-1, k)可以计算总共有多少个k元素子集，也有一些迭代方式可以实现，但是当我尝试想出一个递归解决方案时就卡住了。有人能给我一些提示吗？ 谢谢！

- user497302

---

你应该了解一下格雷码。 - Damian Leszczyński - Vash

你会如何迭代地完成它，以及迭代有什么问题？ - user325117

@MB，因为这是作业要求的内容。我猜想是这个原因。 - The Archetypal Paul

@MB，在迭代中没有魔法发生。简单的话是无聊的。 - Damian Leszczyński - Vash

@Woot4Moo：我提供了一些代码示例，你可以参考一下。 - andersoj

Answer 1

对于集合中的每个元素，取该元素，然后依次将剩余的N-1个元素集的所有(k-1)子集加入其中。

“那是一个黑暗而狂风肆虐的夜晚，船长说…”

- The Archetypal Paul

---

我真的需要一个将其转换为递归方法的想法，因为如上所述，我有一个涉及嵌套循环的迭代解决方案，但不知道如何将其转换为递归方法。 - user497302

这是一个递归方法！它表明产生N集的k子集的问题与取N的每个元素，然后计算剩余N-1大小集合的k-1集相同。当K变为1时，计算子集就变得微不足道了。 - The Archetypal Paul

不好意思，你说得对！我本来想评论第二个回答的迭代解决方案，但它消失了，所以我误把评论写在了错误的位置。 - user497302

这里有重复的内容。最好不要有这些。 - gabe

Answer 2

更好的

对于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();
    }   
  }
}

仅限幂集 这可能不太完美，也不是很优雅，但它可以通过递归计算完整的幂集，然后迭代地对其进行大小调整。

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

}

- andersoj

---

@user497302：为什么不呢？它会递归地计算所有的k子集......编译它，就可以正常运行了。 - andersoj

Answer 3

这是一些伪代码。您可以通过在进行递归调用时存储每个调用的值并在递归调用之前检查调用值是否已经存在来减少相同的递归调用。

以下算法将包含除空集之外的所有子集。

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

- kofhearts