如何在Java中递归地生成N元素集合中的所有k元素子集

Question

因此，我试图从给定的N元素集合中找到所有k元素子集的问题。我知道使用公式C（n，k）= C（n-1，k-1）+ C（n-1，k）的k个子集的总数是多少，我也知道如何去做以迭代的方式，但是当我尝试去思考递归解决方案时，我陷入了困境。任何人都可以给我一个提示吗？ 谢谢！

Answer 1

对于集合中的每个元素，取该元素，然后依次添加剩余N-1个元素集合的所有（k-1）个子集。

“这是个月黑风高的夜晚，船长说......”

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

} 

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