CODEWITHSUNDEEP
javaarrays
AlexJia Wang
AlexJia Wang

Reputation: 41

Get all subsets of a set

import java.util.ArrayList;

public class Subset { //Generate all subsets by generating all binary numbers
    public static ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set) {

        ArrayList<ArrayList<Integer>> allsubsets =
            new ArrayList<ArrayList<Integer>>();
        int max = 1 << set.size();             //there are 2 power n 
        for (int i = 0; i < max; i++) {
            ArrayList<Integer> subset = new ArrayList<Integer>();

            int index = 0;
            while (i > 0) {
                if ((i & 1) > 0) {
                    subset.add(set.get(index)); //Add elements to a new ArrayList
                }
                i >>= 1;
                index++;
            }
            allsubsets.add(subset);
        }
        return allsubsets;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<Integer> set = new ArrayList<Integer>(); //Create an ArrayList
        set.add(1);
        set.add(2);

        System.out.println(getSubsets2(set));
    }
}

The result should be [[],[1],[2],[1,2]]

But I can't get the result, the exception is as follows:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Upvotes: 3

Views: 9996

Answers (7)

Paulo Merson
Paulo Merson

Reputation: 14515

Concise solution in Kotlin:

fun powerSet(inputSet: Set<Int>): Set<Set<Int>> {
    // Convert the input set to a list for indexing
    val inputList = inputSet.toList()

    // Calculate number of subsets (2^n)
    val totalSubsets = 1 shl inputSet.size

    // Generate all subsets
    return (0 until totalSubsets).map {
        inputList.filterIndexed { index, _ -> (it and (1 shl index)) != 0 }.toSet()
    }.toSet()
}

fun main() {
    println("The subsets of [1, 2, 3] are " + powerSet(setOf(1, 2, 3)))
    // Will print:
    // The subsets of [1, 2, 3] are [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
}

The response can be easily filtered using Collection's filter or filterNot. For example, to obtain only non-empty subsets, just replace the last line of the powerSet function with:

    }.filter { subset -> subset.isNotEmpty() }.toSet()

Upvotes: 0

Alex Stanovsky
Alex Stanovsky

Reputation: 1376

Here is a Java 8 solution for this question:

public Set<Set<Integer>> getSubsets(Set<Integer> set) {
    if (set.isEmpty()) {
       return Collections.singleton(Collections.emptySet());
    }

    Set<Set<Integer>> subSets = set.stream().map(item -> {
        Set<Integer> clone = new HashSet<>(set);
        clone.remove(item);
        return clone;
    }).map(group -> getSubsets(group))
            .reduce(new HashSet<>(), (x, y) -> {
                x.addAll(y);
                return x;
            });

    subSets.add(set);
    return subSets;
}

Upvotes: 2

kofhearts
kofhearts

Reputation: 3794

how about a recursive solution? 

vector<vector<int> > getSubsets(vector<int> a){


//base case
    //if there is just one item then its subsets are that item and empty item
    //for example all subsets of {1} are {1}, {}

    if(a.size() == 1){
        vector<vector<int> > temp;
        temp.push_back(a);

        vector<int> b;
        temp.push_back(b);

        return temp;

    }
    else
    {


         //here is what i am doing

         // getSubsets({1, 2, 3})
         //without = getSubsets({1, 2})
         //without = {1}, {2}, {}, {1, 2}

         //with = {1, 3}, {2, 3}, {3}, {1, 2, 3}

         //total = {{1}, {2}, {}, {1, 2}, {1, 3}, {2, 3}, {3}, {1, 2, 3}}

         //return total

        int last = a[a.size() - 1];

        a.pop_back();

        vector<vector<int> > without = getSubsets(a);

        vector<vector<int> > with = without;

        for(int i=0;i<without.size();i++){

            with[i].push_back(last);

        }

        vector<vector<int> > total;

        for(int j=0;j<without.size();j++){
            total.push_back(without[j]);
        }

        for(int k=0;k<with.size();k++){
            total.push_back(with[k]);
        }


        return total;
    }


}

Upvotes: 0

user314104
user314104

Reputation: 1538

Your while loop is incorrect.

Made slightly more succinct with a for-loop:

import java.util.ArrayList;

public class Subset { //Generate all subsets by generating all binary numbers
    public static ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set) {

        ArrayList<ArrayList<Integer>> allsubsets =
        new ArrayList<ArrayList<Integer>>();
        int max = 1 << set.size();             //there are 2 power n different subsets

        for (int i = 0; i < max; i++) {
            ArrayList<Integer> subset = new ArrayList<Integer>();
            for (int j = 0; j < set.size(); j++) {
                if (((i >> j) & 1) == 1) {
                    subset.add(set.get(j));
                }
            }
            allsubsets.add(subset);
        }
        return allsubsets;
    }

    public static void main(String[] args) {
        ArrayList<Integer> set = new ArrayList<Integer>(); //Create an ArrayList
        set.add(1);
        set.add(2);

        System.out.println(getSubsets2(set));
    }
}

Bear in mind that the subset operation is exponential, so you'll get a very large number of elements. The implementation above will only work with about 32 input elements, as that yields 2^32 output subsets, which will very easily run you over the limit of an array...

Upvotes: 7

Stephen C
Stephen C

Reputation: 719416

In a nutshell, your inner while-loop is changing the outer for-loop's loop variable (i). This is disrupting the outer loop iteration. At the end of the inner loop the value of i is going to be zero ... which means that the outer loop will never terminate.

Given what you are doing, the fix is to use a different variable (say j) for the inner loop, and initialize it from i.

This illustrates why it is a bad idea to change a for-loop variable inside the loop.

Upvotes: 0

Wug
Wug

Reputation: 13196

Your problem appears to be in your loop. If you look at it:

for (int i = 0; i < max; i++) {
    ArrayList<Integer> subset = new ArrayList<Integer>();
    int index = 0;
    while (i > 0) {
        if ((i & 1) > 0) {
            subset.add(set.get(index)); //Add elements to a new ArrayList
        }
        i >>= 1;
        index++;
    }
    allsubsets.add(subset);
}

You'll notice that the outside for-loop is trying to count i upwards from zero, and the inner while loop counts it back to zero every iteration, so the outer loop runs forever.

Upvotes: 2

Erdin&#231; Taşkın
Erdin&#231; Taşkın

Reputation: 1578

Program runs forever. Below statement execute continuesly and getting outOfMemory. Variable i value is never bigger than max value, check it. 

`subset.add(set.get(index));`

Upvotes: 0

Related Questions