Power generation recursively without any cycles

Question

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

For example: PowerSet ("abc") prints abc, ab, ac, bc, a, b, c

I saw some recursive solutions with loops, but loops are not allowed in this case.

Any ideas?

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

Answer 1

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

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

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

Recursively, P ( abc ) = { abc } + P ( ab ) + P ( ac ), etc.

The first approach in pseudo code might be:

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

Recursion ends when the row is empty (because it never enters the loop).

If you really need no loops, you will have to convert this 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 implements a recursive function P , which either removes the first character from its argument, or does not. (Here + means set union,. Means concatenation, and λ is an empty string)

 P(abcd) = P(bcd) + aP(bcd) P(bcd) = P(cd) + bP(cd) P(cd) = P(d) + cP(d) P(d) = λ+d //particular case 

Then

 P(d) = λ+d R(cd) = P(d) + cP(d) = λ + d + c.(λ+d) = λ + d + c + cd R(bcd) = P(cd) + bP(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 cycles are enabled, then P disables the power-up function. Otherwise, we need a one-parameter loop function to concatenate the given character into a given set of strings (which, obviously, are two ).

Some tweaking may be possible when playing with String.replace (if you want the result of String or replacing Set with List (so the "extra" parameter is actually the first item in the list).

Answer 2

Well, if you don't have loops, emulate one with recursion using iterators, it's pretty 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 3

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 4

Recursive version of the universal 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 am extracting the recursive addSets method to convert the source 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 5

 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 6

A simple solution, but with poor time complexity (2 ^ n) is this: (just remember one thing when we should avoid (i.e. 0), and as soon as we should 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

Just for fun - the version in which the power elements of any set are stored in LinkedList (to simplify the removal of the head element). Java threads perform 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 simplify:

 (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 8

Based on the information here , here is a solution in C #.

NOTE. The loop in the main function is simply outputting the result to the console value. There are no tags 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); }