如何在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; 
    } 
}