Obtaining a powerset of a set in Java

Manuel_28802 0
Viewed 79381

The powerset of {1, 2, 3} is:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

Let's say I have a Set in Java:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);

How do I write the function getPowerset, with the best possible order of complexity? (I think it might be O(2^n).)

powerset set algorithm java
27 Answers

A sub-set of t is any set that can be made by removing zero or more elements of t. The withoutFirst subset adds the subsets of t that are missing the first element and the for loop will deal with adding subsets with the first element. For example, if t contained the elements ["1", "2", "3"], missingFirst will add [[""], ["2"], ["3"], ["2","3"]] and the for loop will stick the "1" in front of these element and add it to the newSet. So we'll end up with [[""], ["1"], ["2"], ["3"], ["1", "2"], ["1", "3"], ["2","3"], ["1", "2", "3"]].

public static Set<Set<String>> allSubsets(Set<String> t) {
        Set<Set<String>> powerSet = new TreeSet<>();
        if(t.isEmpty()) {
            powerSet.add(new TreeSet<>());
            return powerSet;
        }
        String first = t.get(0);
        Set<Set<String>> withoutFirst = allSubsets(t.subSet(1, t.size()));
        for (List<String> 1st : withoutFirst) {
            Set<String> newSet = new TreeSet<>();
            newSet.add(first);
            newSet.addAll(lst);
            powerSet.add(newSet);
        }
        powerSet.addAll(withoutFirst);
        return powerSet;
    }
user_90116050

Here is to generate a power set. The idea is first = S[0] and smaller sets be S[1,...n].

Compute all subsets of smallerSet and put them in allsubsets.

For each subsets in allsubsets, clone it and add first to the subset.

ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set, int index){
    ArrayList<ArrayList<Integer>> allsubsets;
    if(set.size() == index){
        allsubsets = new ArrayList<ArrayList<Integer>>();
        allsubsets.add(new ArrayList<Integer>()); // the 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);

        }

        moresubsets.addAll(moresubsets);

    }

    return allsubsets;
}
Admin1 
package problems;

import java.util.ArrayList;
import java.util.List;

public class SubsetFinderRecursive {
    public static void main(String[] args) {
        //input
        int[] input = new int[3];
        for(int i=0; i<input.length; i++) {
            input[i] = i+1;
        }
        // root node of the tree
        Node root = new Node();

        // insert values into tree
        for(int i=0; i<input.length; i++) {
            insertIntoTree(root, input[i]);
        }

        // print leaf nodes for subsets
        printLeafNodes(root);
    }

    static void printLeafNodes(Node root) {

        if(root == null) {
            return;
        }

        // Its a leaf node
        if(root.left == null && root.right == null) {
            System.out.println(root.values);
            return;
        }

        // if we are not at a leaf node, then explore left and right

        if(root.left !=null) {
            printLeafNodes(root.left);
        }

        if(root.right != null) {
            printLeafNodes(root.right);
        }
    }

    static void insertIntoTree(Node root, int value) {

        // Error handling
        if(root == null) {
            return;
        }

        // if there is a sub tree then go down
        if(root.left !=null && root.right != null) {
            insertIntoTree(root.left, value);
            insertIntoTree(root.right, value);
        }

        // if we are at the leaf node, then we have 2 choices
        // Either exclude or include
        if(root.left == null && root.right == null) {
            // exclude
            root.left = new Node();
            root.left.values.addAll(root.values);
            // include
            root.right = new Node();
            root.right.values.addAll(root.values);
            root.right.values.add(value);
            return;
        }
    }

}

class Node {
    Node left;
    Node right;
    List<Integer> values = new ArrayList<Integer>();
}
user_60549850

This function solved this problem by recursion but make variable named powerset as a Global Variable:

static ArrayList<ArrayList<Integer>> powerSet = new ArrayList<>();

public static void getPowerSet(Queue<Integer> a) {
    int n = a.poll();
    if (!a.isEmpty()) {
        getPowerSet(a);
    }
    int s = powerSet.size();
    for (int i = 0; i < s; i++) {
        ArrayList<Integer> ne = new ArrayList<>();
        for (int j = 0; j < powerSet.get(i).size(); j++) {
            ne.add(powerSet.get(i).get(j));
        }
        ne.add(n);
        powerSet.add(ne);
    }
    ArrayList<Integer> p = new ArrayList<>();
    p.add(n);
    powerSet.add(p);
}
user_177511970
Related