Power Set | GeeksforGeeks
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
Time Complexity: O(n2^n)
http://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/
http://www.zrzahid.com/power-set-or-super-set-of-a-list/
Recursive: Include or exclude.
http://rosettacode.org/wiki/Power_set#Java
Iterative:
public static Set<Set<Integer>> findPowerSet(Set<Integer> orgs) {
Set<Set<Integer>> power = new HashSet<>();
power.add(new HashSet<>()); //empty?
for (Integer i : orgs) {
Set<Set<Integer>> temp = new HashSet<>();
for (Set<Integer> subSets : power) {
Set<Integer> cur = new HashSet<Integer>(subSets);
cur.add(i);
temp.add(cur);
}
power.addAll(temp);
}
return power;
}
http://comproguide.blogspot.com/2013/10/program-to-find-powerset-of-given-set.html
Arraylist<Arraylist<Integer> > getSubsets(Arraylist<Integer> set, int index) {
Arraylist<Arraylist<Integer> > allsubsets;
if (set.size()== index) {//Base case - add empty set
allsubsets = new Arraylist<Arraylist<Integer> >();
allsubsets.add(new Arraylist<Integer>()); // Empty set
} else {
allsubsets = getSubsets(set, index+ 1);
int item= set.get(index);
Arraylist<Arraylist<Integer> > moresubsets
new Arraylist<Arraylist<Integer> >();
for (Arraylist<Integer> subset : allsubsets) {
Arraylist<Integer> newsubset = new Arraylist<Integer>();
newsubset.addAll(subset); //
newsubset.add(item);
moresubsets.add(newsubset);
}
allsubsets.addAll(moresubsets);
}
return allsubsets;
}
Arraylist<Arraylist<Integer> > getSubsets2(ArrayList<Integer> set) {
ArrayList<ArrayList<Integer> > allsubsets = new Arraylist<Arraylist<Integer> >();
int max= 1 << set.size(); /* Compute 2An */
for (int k = 0; k < max; k++ ) {
ArrayList<Integer> subset= convertintToSet(k, set);
allsubsets.add(subset);
}
return allsubsets;
}
Arraylist<Integer> convertlntToSet(int x, Arraylist<Integer> set) {
Arraylist<Integer> subset = new Arraylist<Integer>();
int index = 0;
for (int k = x; k > 0; k >>= 1) {
if ((k & 1) == 1) {
subs et.add(set.get(index));
}
index++;
}
return subset;
}
http://www.geeksforgeeks.org/find-distinct-subsets-given-set/
http://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/
For an array of size n, we have 2^n sub-sequences (including empty) in total. Observe, in total 2nsub-sequences, each elements occurs 2n-1 times.
Read full article from Power Set | GeeksforGeeks
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
Time Complexity: O(n2^n)
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
Binary Stringhttp://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/
// Print all subsets of given set[] static void printSubsets(char set[]) { int n = set.length; // Run a loop for printing all 2^n // subsets one by obe for (int i = 0; i < (1<<n); i++) { System.out.print("{ "); // Print current subset for (int j = 0; j < n; j++) // (1<<j) is a number with jth bit 1 // so when we 'and' them with the // subset number we get which numbers // are present in the subset and which // are not if ((i & (1 << j)) > 0) System.out.print(set[j] + " "); System.out.println("}"); } }
Notice that, if we represent each unique letters by a bit position in a n bit integer than the power set will look like, for example for n=3,
{} -> 000
{a} -> 001
{b} -> 010
{c} -> 100
{a, b} -> 011
{b, c} -> 110
{a, c} -> 101
{a,b,c}-> 111
That is we can generate the power set of n numbers by looking at the bit positions n bit integers. So, we will basically take each integer from 0 to 2^n-1 and for each we will check the bit positions set. Each number corresponds to a set in the superset and each set bit position will contribute to an element in the set. Below is the implementation of this idea which runs in O(n*2^n) time and O(1) space.
public static List<List<Character>> powerSet(char[] chars){ int n = chars.length; List<List<Character>> powerSet = new ArrayList<List<Character>>(); //superSet.add(Collections.emptyList()); if(n == 0){ return powerSet; } int max = (int)Math.pow(2, n); for(int i = 0; i<max; i++){ List<Character> set = new ArrayList<Character>(); for(int j = 0; j<n; j++){ if((i & (1<<j)) > 0){ set.add(chars[j]); } } powerSet.add(set); } return powerSet; }
public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet( LinkedList<T> A){ LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>(); int ansSize = (int)Math.pow(2, A.size()); for(int i= 0;i< ansSize;++i){ String bin= Integer.toBinaryString(i); //convert to binary while(bin.length() < A.size()) bin = "0" + bin; //pad with 0's LinkedList<T> thisComb = new LinkedList<T>(); //place to put one combination for(int j= 0;j< A.size();++j){ if(bin.charAt(j) == '1')thisComb.add(A.get(j)); } Collections.sort(thisComb); //sort it for easy checking ans.add(thisComb); //put this set in the answer list } return ans; }http://algorithms.tutorialhorizon.com/print-all-the-subsets-of-a-given-set-power-set/
Recursive: Include or exclude.
public void combinations(int[] A, int x) { if (x == A.length - 1) { A[x] = 0; // last digit, don't select it printArray(A); // print the set A[x] = 1; //// last digit, select it printArray(A); return; } A[x] = 0; //either you will not select this digit combinations(A, x + 1); A[x] = 1; //either you will select this digit combinations(A, x + 1); } public void printArray(int[] A) { boolean isNULL = true; System.out.print("{"); for (int i = 0; i < B.length; i++) { if (A[i] == 1) { System.out.print(B[i] + ""); isNULL = false; } } if (isNULL == false) { System.out.print("}"); System.out.print(" "); } if (isNULL) { System.out.print("Empty"); System.out.print("} "); } }Iterative:
public static <T> List<List<T>> powerset(Collection<T> list) { List<List<T>> ps = new ArrayList<List<T>>(); ps.add(new ArrayList<T>()); // add the empty set // for every item in the original list for (T item : list) { List<List<T>> newPs = new ArrayList<List<T>>(); for (List<T> subset : ps) { // copy all of the current powerset's subsets newPs.add(subset); // plus the subsets appended with the current item List<T> newSubset = new ArrayList<T>(subset); newSubset.add(item); newPs.add(newSubset); } // powerset is now powerset of list.subList(0, list.indexOf(item)+1) ps = newPs; } return ps; }https://gist.github.com/lostMohican/4a768cbe74e0eed0c00e
public static Set<Set<Integer>> findPowerSet(Set<Integer> orgs) {
Set<Set<Integer>> power = new HashSet<>();
power.add(new HashSet<>()); //empty?
for (Integer i : orgs) {
Set<Set<Integer>> temp = new HashSet<>();
for (Set<Integer> subSets : power) {
Set<Integer> cur = new HashSet<Integer>(subSets);
cur.add(i);
temp.add(cur);
}
power.addAll(temp);
}
return power;
}
http://comproguide.blogspot.com/2013/10/program-to-find-powerset-of-given-set.html
Arraylist<Arraylist<Integer> > getSubsets(Arraylist<Integer> set, int index) {
Arraylist<Arraylist<Integer> > allsubsets;
if (set.size()== index) {//Base case - add empty set
allsubsets = new Arraylist<Arraylist<Integer> >();
allsubsets.add(new Arraylist<Integer>()); // Empty set
} else {
allsubsets = getSubsets(set, index+ 1);
int item= set.get(index);
Arraylist<Arraylist<Integer> > moresubsets
new Arraylist<Arraylist<Integer> >();
for (Arraylist<Integer> subset : allsubsets) {
Arraylist<Integer> newsubset = new Arraylist<Integer>();
newsubset.addAll(subset); //
newsubset.add(item);
moresubsets.add(newsubset);
}
allsubsets.addAll(moresubsets);
}
return allsubsets;
}
Recall that when we're generating a set, we have two choices for each element: (1) the element is in the set (the "yes" state) or (2) the element is not in the set (the "no" state). This means that each subset is a sequence of yeses I nos-e.g., "yes, yes, no, no, yes, no"
Arraylist<Arraylist<Integer> > getSubsets2(ArrayList<Integer> set) {
ArrayList<ArrayList<Integer> > allsubsets = new Arraylist<Arraylist<Integer> >();
int max= 1 << set.size(); /* Compute 2An */
for (int k = 0; k < max; k++ ) {
ArrayList<Integer> subset= convertintToSet(k, set);
allsubsets.add(subset);
}
return allsubsets;
}
Arraylist<Integer> convertlntToSet(int x, Arraylist<Integer> set) {
Arraylist<Integer> subset = new Arraylist<Integer>();
int index = 0;
for (int k = x; k > 0; k >>= 1) {
if ((k & 1) == 1) {
subs et.add(set.get(index));
}
index++;
}
return subset;
}
http://www.geeksforgeeks.org/find-distinct-subsets-given-set/
Given a set of positive integers, find all its subsets. The set can contain duplicate elements, so any repeated subset should be considered only once in the output.
Examples:
Input: S = {1, 2, 2}
Output: {}, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}
The idea is to use a bit-mask pattern to generate all the combinations as discussed in previous post. But previous post will print duplicate subsets if the elements are repeated in the given set. To handle duplicate elements, we construct a string out of given subset such that subsets having similar elements will result in same string. We maintain a list of such unique strings and finally we decode all such string to print its individual elements.
// Utility function to split the string using a delim. Refer -vector<string> split(const string &s, char delim){ vector<string> elems; stringstream ss(s); string item; while (getline(ss, item, delim)) elems.push_back(item); return elems;}// Function to find all subsets of given set. Any repeated// subset is considered only once in the outputint printPowerSet(int arr[], int n){ vector<string> list; /* Run counter i from 000..0 to 111..1*/ for (int i = 0; i < (int) pow(2, n); i++) { string subset = ""; // consider each element in the set for (int j = 0; j < n; j++) { // Check if jth bit in the i is set. If the bit // is set, we consider jth element from set if ((i & (1 << j)) != 0) subset += to_string(arr[j]) + "|"; } // if subset is encountered for the first time // If we use set<string>, we can directly insert if (find(list.begin(), list.end(), subset) == list.end()) list.push_back(subset); } // consider every subset for (string subset : list) { // split the subset and print its elements vector<string> arr = split(subset, '|'); for (string str: arr) cout << str << " "; cout << endl; }}For an array of size n, we have 2^n sub-sequences (including empty) in total. Observe, in total 2nsub-sequences, each elements occurs 2n-1 times.
Given an array of n integers. The task is to find the sum of sum of each of sub-sequence of the array.
int sum(int arr[], int n){ int ans = 0; // Finding sum of the array. for (int i = 0; i < n; i++) ans += arr[i]; return ans * pow(2, n - 1);}