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.

Solution 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).

Solution 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');

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

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

View more solutions

Comments

[uohzxela]

Awesome, I did think of the algorithm in your pseudocode. But I got stuck at performing this task: let substring = string excluding char. Is there any built-in functions in the API to do that?

[Javier]

s.substring(0,pos) will return the substring from 0 to pos-1, and s.substring(pos) will return the substring from pos to the end of the string.

[uohzxela]

Thanks. I get it. Anyway, I'm being pedantic because the question only mentioned one parameter. Do you know how to implement the method with only one parameter which is the the String input?

[Javier]

I proposed another approach which is nicer in terms of recursion, but still needs loops. This article seems to contain the answer, but I cannot download it dl.acm.org/citation.cfm?id=1151793

[uohzxela]

Seems like the question's requirement extends beyond to the research domain. Thank you so much for providing the link. I'll peruse it and see what I can do with it.

[fons]

You cannot get better complexity than 2^n since there are 2^n possible subsets.

[Artem Stepanenko]

@Javier "(plus the set abc itself )" – shouldn't it be abcd and an empty subset instead?

[Javier]

@ArtemStepanenko thanks! I fixed the typo. About the empty set, it's not only a member of P(abcd), but also of P(abc), etc.

[melpomene]

In the same spirit, an even simpler solution in Haskell: powerSet = filterM (\_ -> [True, False])

[Varun]

I really liked how you excluded from the loop from the equation, +1 for that