How to create all subsets of k-elements from a set of N-elements recursive in Java

Question

So, I'm stuck with this problem, trying to find all subsets of k-elements from a given set of N-elements. I know that the total number of k-subsets uses the formula C (n, k) = C (n-1, k-1) + C (n-1, k), and I also have an idea how to do this in iterative mode, but I get stuck when I try to think of a recursive solution. Can someone give me a hint? Thank you

Answer 1

For each element in the set, take this element, then add in turn all (k-1) subsets of the remaining set of elements 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();
    }   
  }
}

, , , , () .

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

Here is some pseudo code. You can cut out the same recursive calls by storing the values ​​for each call as you go, and before the recursive call checks to see if the call value is already present.

The following algorithm will have all subsets excluding the empty set.

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