Algorithm:
If S = (a, b, c) then the powerset(S) is the set of all subsets
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
The first "trick" is to try to define recursively.
What would be a stop state?
S = () has what powerset(S)?
How get to it?
Reduce set by one element
Consider taking an element out - in the above example, take out {c}
S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }
What is missing?
powerset(S) = { (c), (a,c), (b,c), (a,b,c)}
hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
take any element out
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS
powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}
powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))
where ei is an element of S (a singleton)
Pseudo-algorithm
Go backwards:
powerset(S) when S = {()} is {()}
powerset(S) when S = {(a)} is {(), (a)}
powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}
etc...
Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If S has n elements in it then P(s) will have 2^n elements
1st using Recursion
public class PowerSet {
private void printPowerSet(String inputString, String prefixString, int startIndex){
if(inputString == null){
return;
}
for(int i=startIndex;iString str = "";
str = prefixString + inputString.charAt(i);
System.out.println("{" + str + "}\n");
printPowerSet(inputString, str, i+1);
}
}
public static void main(String args[]){
String inputStr ="123";
System.out.println("{ }\n");
for(int i=0; iPowerSet powerSet = new PowerSet();
System.out.println("{" + inputStr.charAt(i) + "}\n");
powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);
}
}
}
TC O(n^2)
Sc O(n)
Run here https://ideone.com/8RuF1
2nd Iterative Method
Algorithm:
Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline
Example:
Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111
Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc
#include
#include
void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;
/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1< printf("%c", set[j]);
}
printf("\n");
}
}
/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c','d'};
printPowerSet(set, 4);
getchar();
return 0;
}
TC O(n*2^n)
SC O(1)
Rune Here https://ideone.com/z5tHG
Java program for Doing The Same
class PowerSet {
int arr[]={1,2,3};
int number=0;
void powerSet(){
for(int i=0;iint k=i;
int counter=0;
while(k>0){
if((k & 1) == 1){
System.out.print(arr[counter]);
}
counter++;
k=k>>1;
}
System.out.println();
number++;
}
}
public static void main(String[] args) {
PowerSet p=new PowerSet();
p.powerSet();
System.out.println("Total number of subsets are"+p.number);
}
}
Run Here https://ideone.com/LtjsT
More
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html
http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java
http://rosettacode.org/wiki/Power_set
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/
http://www.roseindia.net/tutorial/java/core/powerset.html
http://shriphani.com/blog/2008/03/31/one-step-forward-two-steps-back/
http://planetmath.org/?op=getobj&from=objects&id=136
Powerset: A recursive algorithm
If S = (a, b, c) then the powerset(S) is the set of all subsets
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
The first "trick" is to try to define recursively.
What would be a stop state?
S = () has what powerset(S)?
How get to it?
Reduce set by one element
Consider taking an element out - in the above example, take out {c}
S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }
What is missing?
powerset(S) = { (c), (a,c), (b,c), (a,b,c)}
hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
take any element out
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS
powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}
powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))
where ei is an element of S (a singleton)
Pseudo-algorithm
Go backwards:
powerset(S) when S = {()} is {()}
powerset(S) when S = {(a)} is {(), (a)}
powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}
etc...
Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If S has n elements in it then P(s) will have 2^n elements
1st using Recursion
public class PowerSet {
private void printPowerSet(String inputString, String prefixString, int startIndex){
if(inputString == null){
return;
}
for(int i=startIndex;i
str = prefixString + inputString.charAt(i);
System.out.println("{" + str + "}\n");
printPowerSet(inputString, str, i+1);
}
}
public static void main(String args[]){
String inputStr ="123";
System.out.println("{ }\n");
for(int i=0; i
System.out.println("{" + inputStr.charAt(i) + "}\n");
powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);
}
}
}
TC O(n^2)
Sc O(n)
Run here https://ideone.com/8RuF1
2nd Iterative Method
Algorithm:
Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline
Example:
Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111
Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc
#include
#include
void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;
/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1<
}
printf("\n");
}
}
/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c','d'};
printPowerSet(set, 4);
getchar();
return 0;
}
TC O(n*2^n)
SC O(1)
Rune Here https://ideone.com/z5tHG
Java program for Doing The Same
class PowerSet {
int arr[]={1,2,3};
int number=0;
void powerSet(){
for(int i=0;i
int counter=0;
while(k>0){
if((k & 1) == 1){
System.out.print(arr[counter]);
}
counter++;
k=k>>1;
}
System.out.println();
number++;
}
}
public static void main(String[] args) {
PowerSet p=new PowerSet();
p.powerSet();
System.out.println("Total number of subsets are"+p.number);
}
}
Run Here https://ideone.com/LtjsT
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html
http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java
http://rosettacode.org/wiki/Power_set
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/
http://www.roseindia.net/tutorial/java/core/powerset.html
http://shriphani.com/blog/2008/03/31/one-step-forward-two-steps-back/
http://planetmath.org/?op=getobj&from=objects&id=136
1 comment :
Void printSubsets(ArrayList soFar, ArrayList Rest)
{
if (Rest.Length==0)
Console.WriteLine(soFar);
printSubsets(soFar + Rest.get(0), Rest.RemoveAt(0))
printSubsets(soFar, Rest.RemoveAt(0));
}
here the logic behind this code is recursively remove an element from the array of numbers and add it to an empty set in all possible combinations.
import java.util.*;
class PowerSet
{
static void printSubsets(ArrayList soFar, ArrayList Rest)
{
int i=0;
if (Rest.size()==0)
System.out.println(soFar);
printSubsets(soFar.add(i++,Rest.get(0)),Rest.remove(0));
printSubsets(soFar, Rest.remove(0));
}
public static void main(String a[])
{
ArrayList soFar=new ArrayList();
ArrayList Rest=new ArrayList();
Rest.add(123);
printSubsets(soFar,Rest);
}
}
Post a Comment