Bagaimana untuk Menjana Set Kuasa Set Java dengan Cekap?

Mendapatkan Set Kuasa Set dalam Java dengan Kerumitan Optimum

Set kuasa set ialah koleksi semua subset set itu. Untuk set dengan n elemen, set kuasa mengandungi 2^n subset.

Mari kita pertimbangkan set Java:

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

Kami ingin menulis fungsi, getPowerset, untuk menjana set kuasa bagi set ini. Kerumitan ideal untuk operasi ini ialah O(2^n).

Satu pelaksanaan yang mungkin menggunakan generik dan set Java ialah:

public static <T> Set<Set<T>> getPowerset(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<>());
        return sets;
    }
    List<T> list = new ArrayList<>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<>(list.subList(1, list.size()));

    for (Set<T> set : getPowerset(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }

    return sets;
}

Penyelesaian rekursif ini berulang melalui elemen set, menambahkannya pada setiap subset dan menjana subset baharu. Ia secara konsisten mengekalkan set kuasa elemen yang tinggal.

Ujian mudah menggunakan input contoh menghasilkan hasil yang dijangkakan:

for (Set<Integer> s : getPowerset(mySet)) {
    System.out.println(s);
}

Output:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Atas ialah kandungan terperinci Bagaimana untuk Menjana Set Kuasa Set Java dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!