Generating power set recursively without any loops

Question

How do you write a recursive method PowerSet(String input) that prints out all possible combinations of a string that is passed to it?

For example: PowerSet("abc") will print out abc, ab, ac, bc, a, b, c

I have seen some recursive solutions with loops, but in this case no loops are allowed.

Any ideas?

Edit: The required method has only one parameter, i.e. String input.

Answer 1

The powerset of abcd is the union of the power-sets of abc, abd, acd (plus the set abcd itself*).

 P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`)

_{* Note that the empty set, which is a member of P(abcd) is also a member of P(abc), P(abd), ... so the equivalence stated above holds.}

Recursively, P(abc) = {abc} + P(ab) + P(ac), and so on

A first approach, in pseudocode, could be:

powerset(string) {
  add string to set;
  for each char in string {
   let substring = string excluding char,
   add powerset(substring) to set
  }
  return set;      
}

The recursion ends when the string is empty (because it never enters the loop).

If your really want no loops, you will have to convert that loop to another recursion. Now we want to generate ab, ac and cb from abc

powerset(string) {
  add string to set;
  add powerset2(string,0) to set;
  return set
}

powerset2(string,pos) {
  if pos<length(string) then
    let substring = (string excluding the char at pos)
    add powerset(substring) to set
    add powerset2(string,pos+1) to set
  else 
    add "" to set
  endif
  return set
}

Another approach implement a recursive function P that either removes the first character from its argument, or does not. (Here + means set union, . means concatenation and λ is the empty string)

P(abcd) = P(bcd) + a.P(bcd)
P(bcd)  = P(cd)  + b.P(cd)
P(cd)   = P(d)   + c.P(d)
P(d)    = λ+d //particular case

Then

P(d)    = λ+d
R(cd)   = P(d)  + c.P(d)  = λ + d + c.(λ+d) = λ + d + c + cd
R(bcd)  = P(cd) + b.P(cd) = λ + d + c + cd + b.(λ + d + c + cd)
                          = λ + d + c + cd + b + bd + bc + bcd
P(abcd) =  λ +  d +  c +  cd +  b +  bd +  bc +  bcd 
        + aλ + ad + ac + acd + ab + abd + abc + abcd 

If loops were allowed, then P is out power-set function. Otherwise, we would need a one-parameter loopless function for concatenating a given character to a given set of strings (which obviously are two things).

Some tweak could be possible by playing with String.replace (if a String result is desired, or by replacing Set with List (so that the "additional" parameter is actually the first element in the list).

Answer 2

This will also do the trick:

var powerset = function(arr, prefix, subsets) {
  subsets = subsets || [];
  prefix = prefix || [];
  if (arr.length) {
    powerset(arr.slice(1), prefix.concat(arr[0]), subsets);
    powerset(arr.slice(1), prefix, subsets);
  } else {
    subsets.push(prefix);
  }
  return subsets;
};

powerset('abc');

Answer 3

Well if you don't have loops, emulate one with recursion, using iterators this is acutally quite simple.

    public final Set<Set<Integer>> powerSet(Set<Integer> set) {
        Set<Set<Integer>> powerSet = new HashSet<>();
        powerSet(set, powerSet, set.iterator());
        return powerSet;
    }
    public final void powerSet(Set<Integer> set, Set<Set<Integer>> powerSet, Iterator<Integer> iterator) {
        if(iterator.hasNext()) {
            Integer exlude = iterator.next();
            Set<Integer> powThis = new HashSet<Integer>();
            powThis.addAll(set);
            powThis.remove(exlude);
            powerSet.add(powThis);
            powerSet(powThis, powerSet, powThis.iterator());
            powerSet(set, powerSet, iterator);
        }
    }
//usage
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        log.error(powerSet(set).toString());

Answer 4

A recursive version of the generic solution proposed by João Silva :

public static <T> Set<Set<T>> powerSet2(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
    addSets(sets, powerSet(rest), head);
    return  sets;
}

private static <T> void addSets(Set<Set<T>> sets, Set<Set<T>> setsToAdd, T head) {
    Iterator<Set<T>> iterator = setsToAdd.iterator();
    if (iterator.hasNext()) {
        Set<T> set = iterator.next();
        iterator.remove();
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
        addSets(sets, setsToAdd, head);
    }
}

I extract the recursive addSets method to transform the original for loop:

for (Set<T> set : powerSet(rest)) {
    Set<T> newSet = new HashSet<T>();
    newSet.add(head);
    newSet.addAll(set);
    sets.add(newSet);
    sets.add(set);
}