Comment générer tous les sous-ensembles de k-éléments à partir d'un ensemble d'éléments N récursivement en Java

Question

Je suis donc bloqué par ce problème d'essayer de trouver tous les sous-ensembles k-éléments d'un ensemble N-éléments donné. Je sais ce que le nombre total de k-sous-ensembles utilise la formule C (n, k) = C (n-1, k-1) + C (n-1, k) et j'ai aussi une idée de comment le faire d'une manière itérative, mais je reste coincé quand j'essaie de penser à une solution récursive. Quelqu'un peut-il me donner un indice? Merci!

Answer 1

Pour chaque élément de l'ensemble, prenez cet élément, puis ajoutez à tour de rôle tous les sous-ensembles (k-1) de l'ensemble d'éléments N-1 restant.

« Ce fut une nuit sombre et orageuse, et le capitaine dit ... »

Answer 2

Mieux

Ceci est rompu pour la k=0 cas, parce que je pense que ça va revenir un ensemble contenant l'ensemble vide, ce qui n'est pas tout à fait correct. En tous cas. Il y a aussi une itération ici, vous pourriez probablement remplacer cela par une récursion si le but est PUREMENT Récursif. Ceci est une modification assez simple de l'algorithme donné à wikipedia: powerset. Je vais laisser les casse-coin (k = 0) au lecteur.

Cette opération n'est pas correctement récursive en aval, ce qui n'est pas le cas dans la plupart des machines virtuelles Java. (Je suppose que la machine virtuelle Java IBM fait cela ...)

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

Puissance Situé à seulement Cela ne probablement pas tout à fait y arriver, et pas vraiment élégant, mais il calcule la powerset pleine récursive, puis le coupe (itérativement) pour la taille.

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

Voici un pseudo-code. Vous pouvez couper les mêmes appels récursifs en stockant les valeurs de chaque appel au fur et à mesure et avant la vérification d'appel récursive si la valeur d'appel est déjà présente.

L'algorithme suivant aura tous les sous-ensembles à l'exclusion de l'ensemble vide.

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