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

Power set (P) of string "abc" contains 2 types of elements: character 'a' itself and its combination with elements of P('bc'). Similarly P('bc') contains character 'b' and its combination with elements of P('c'). And also P('c') contains character 'c' and its combination with null string.

Now make function powerSet(string input, string substring="") This will print the substring and it denotes the combination of first element of input string with substring.

Base Condition: When length of input string is 0 then prints the substring.

Recursive condition: 1). Call powerSet( input[1: input.length()], substring ) #this is for elements of power set of string exluding 0th index character 2). Call powerSet( input[1: input.length()], substring+input[0]) # this is for combination.

#include<iostream>
#include<string>
using namespace std;

void powerSet(string input,string substring){

    if(input.length()==0){
        cout<<substring<<", ";
        return;
    }
    string op1=substring;
    string op2=substring + input[0];    
    powerSet(input.substr(1),op1);
    powerSet(input.substr(1),op2);
    return;
}
int main(){
    string input="abc";
    powerSet(input);
}

Answer 2

PowerSet will print all combinations of elements for example [123] will forms 123,12,13,23,1,2,3

We can find the powerset values easily by using the concept of tree

let add an element or remove an element every time

                    abc
           a                   " "
       ab     a             b       " "
  abc   ab  ac  a         bc   b   c   " "

here first have added a and not added a so tree form "a" and " " subelements now take a constant and add 'b' to it and don't add 'b' then it will create another sub tree for 'a' in the same way the we add and remove element utill we reach the end .

here the method to add element and to remove element powerset(str,i+1,cur+str.charAt(i)); powerset(str,i+1,cur);

import java.io.*;
import java.util.*;
import java.lang.Math;

class Demo{
    
    public static void main(String args[]) {
        String str="123";
        String str1="";
        int r=0;
        powerset(str,r,str1);
        
    }
    
    public static void powerset(String str,int i,String cur){
        
        if(i==str.length()){
            
            System.out.println(cur);
            return;
            
        }
        
        powerset(str,i+1,cur+str.charAt(i));
        powerset(str,i+1,cur);
         
         
    }
    
}

Answer 3

Based on the info here, here is solution in C#.

NOTE: the loop in the main function is just to print the result into the console value. No loops used in the PowerSet method.

    public static void Main(string[] args)
    {

        string input = "abbcdd";


        Dictionary < string, string> resultSet = new Dictionary<string, string>();

        PowerSet(input, "", 0, resultSet);

        //apply sorting 
        var resultSorted = resultSet.OrderBy(l => l.Key.Length).ThenBy(l=>l.Key);

        //print values
        foreach(var keyValue in resultSorted)
        {
            Console.Write("{{{0}}}, ",keyValue.Key);
        }


    }

    /// <summary>
    /// Computes the powerset of a string recursively
    /// based on the Algorithm http://www.ideserve.co.in/learn/generate-all-subsets-of-a-set-recursion
    /// </summary>
    /// <param name="input">Original input string</param>
    /// <param name="temp">Temporary variable to store the current char for the curr call</param>
    /// <param name="depth">The character position we are evaluating to add to the set</param>
    /// <param name="resultSet">A hash list to store the result</param>
    public static void PowerSet(string input, string temp, int depth, Dictionary<string, string> resultSet)
    {

        //base case
        if(input.Length == depth)
        {
            //remove duplicate characters
            string key = new string(temp.ToCharArray().Distinct().ToArray());

            //if the character/combination is already in the result, skip it
            if (!resultSet.ContainsKey(key))
                resultSet.Add(key, key);

            return;//exit 
        }

        //left
        PowerSet(input, temp, depth + 1, resultSet);

        //right
        PowerSet(input, temp + input[depth], depth + 1, resultSet);

    }

Answer 4

Just for fun, a version that does powersets of any set stored in a LinkedList (to make it easy to remove the head element). Java 8 streams do the functional part:

static <T> LinkedList<LinkedList<T>> powerset(LinkedList<T> elements) {
  if (elements.isEmpty()) 
    return copyWithAddedElement(new LinkedList<>(), new LinkedList<>());
  T first = elements.pop();
  LinkedList<LinkedList<T>> powersetOfRest = powerset(elements);
  return Stream.concat(
      powersetOfRest.stream(), 
      powersetOfRest.stream().map(list -> copyWithAddedElement(list, first)))
          .collect(Collectors.toCollection(LinkedList::new));
}

static <T> LinkedList<T> copyWithAddedElement(LinkedList<T> list, T elt) {
  list = new LinkedList<>(list);
  list.push(elt);
  return list;
}

This is inspired by the following Common Lisp, which shows that the right language can make things simpler:

(defun powerset (set)
  (cond ((null set) '(()))
        (t (let ((powerset-of-rest (powerset (cdr set))))
          (append powerset-of-rest
                  (mapcar #'(lambda (x) (cons (car set) x)) 
                          powerset-of-rest))))))

Answer 5

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 6

Simple solution but with poor time complexity(2^n) is as following(just keep one thing in mind once we have to avoid(i.e. 0) and once we have to take it(i.e. 1):

public HashSet<int[]> powerSet(int n) {
    return calcPowerSet(n-1, new HashSet<int[]>(), new int[n]);
}

private HashSet<int[]> calcPowerSet(int n, HashSet<int[]> result, int []set) {
    if(n < 0) {
        result.add(set.clone());
        return null;
    }
    else {
        set[n] = 0;
        calcPowerSet(n-1, result, set);
        set[n] = 1;
        calcPowerSet(n-1, result, set);
        return result;
    }
}

Answer 7

void powerSet(int * ar, int *temp, int n, int level,int index)
{
    if(index==n) return;

    int i,j;
    for(i=index;i<n;i++)
    {
    temp[level]=ar[i];

    for(j=0;j<=level;j++)
    printf("%d ",temp[j]);
    printf("   - - -  t\n");

    powerSet(ar, temp, n, level+1,i+1);
    }
}

int main()
{
    int price[] = {1,2,3,7};
    int temp[4] ={0};

    int n = sizeof(price)/sizeof(price[0]);

    powerSet(price, temp, n, 0,0);


    return 0;
}

Answer 8

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 9

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

Answer 10

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