Как сгенерировать все подмножества k-элементов из набора N-элементов, рекурсивного в Java

Question

Так что я застрял в этой проблеме, пытаясь найти все подмножества k-элементов из заданного набора N-элементов. Я знаю, что общее число k-подмножеств использует формулу C (n, k) = C (n-1, k-1) + C (n-1, k), и у меня также есть идея, как это сделать в итеративном режиме, но я застреваю, когда пытаюсь думать о рекурсивном решении. Может ли кто-нибудь дать мне подсказку? Спасибо!

Answer 1

Для каждого элемента набора возьмите этот элемент, а затем добавьте по очереди все (k-1) подмножества оставшегося набора элементов N-1.

«Это была темная и бурная ночь, и капитан сказал ...»

Answer 2

Лучше

Это сломана для k=0 случае, потому что я думаю, что он будет возвращать набор, содержащий пустое множество, что не совсем правильно. Так или иначе. Здесь также есть итерация, вы, вероятно, замените ее рекурсией, если цель будет PURELY рекурсивной. Это довольно простая модификация алгоритма, приведенного в 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(); 
    } 
    } 
} 

Питание Устанавливают только Это, наверное, не совсем туда добраться, и не очень элегантно, но он вычисляет полный 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; 
    } 
    } 

} 

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