2 
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));
    }
}

结果应该是[[],[1],[2],[1,2]]

但是我无法得到结果，异常如下：

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

6 回答 6

7

您的 while 循环不正确。

使用 for 循环稍微简洁一些：

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));
    }
}

请记住，子集运算是指数的，因此您将获得大量元素。上面的实现只适用于大约 32 个输入元素，因为这会产生 2^32 个输出子集，这很容易让你超过数组的限制......

于 2013-01-08T22:25:27.620 回答
2

您的问题似乎在您的循环中。如果你看它：

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);
}

你会注意到外部的 for 循环试图i从零开始向上计数，而内部的 while 循环每次迭代都将其重新计数为零，因此外部循环永远运行。

于 2013-01-08T22:26:09.353 回答
1

这是针对此问题的 Java 8 解决方案：

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;
}
于 2019-03-10T20:17:54.367 回答
0

简而言之，您的内部 while 循环正在更改外部 for 循环的循环变量 ( i)。这破坏了外循环迭代。在内循环结束时，值i将为零……这意味着外循环永远不会终止。

鉴于您正在执行的操作，解决方法是j为内部循环使用不同的变量（例如 ），并从i.

这说明了为什么在循环内更改 for 循环变量是一个坏主意。

于 2013-01-08T22:30:55.583 回答
0

程序永远运行。下面的语句继续执行并退出内存。变量 i 的值永远不会大于最大值，请检查它。

`subset.add(set.get(index));`
于 2013-01-08T22:22:06.193 回答
0

递归解决方案怎么样？

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;
    }


}
于 2013-09-10T15:51:16.013 回答