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 ループは 0 から上向きにカウントしようとしてiおり、内側の while ループは繰り返しごとにそれを 0 に戻そうとしているため、外側のループは永久に実行されます。

于 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

プログラムは永久に実行されます。以下のステートメントは継続的に実行され、outOfMemory を取得します。変数 i の値が最大値より大きくなることはありません。確認してください。

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

簡単に言えば、内側の while ループが外側の for ループのループ変数 ( i) を変更しています。これにより、外側のループの反復が中断されます。内側のループの最後で、 の値はi0 になります。これは、外側のループが決して終了しないことを意味します。

あなたがしていることを考えると、修正はj、内側のループに別の変数 (たとえば ) を使用し、それを から初期化することですi。

これは、ループ内で for ループ変数を変更することがなぜ悪い考えなのかを示しています。

于 2013-01-08T22:30:55.583 に答える