Bagaimana untuk Mengira Set Kuasa Set dalam Java dengan Cekap?

Pengiraan Set Kuasa untuk Set dalam Java

Dalam sains komputer, set kuasa set mewakili koleksi semua subset yang mungkin bagi set itu. Artikel ini meneroka cara membina set kuasa set integer dalam Java, berusaha untuk kerumitan masa yang optimum.

Pernyataan Masalah

Memandangkan set integer yang ditakrifkan dalam Java , matlamat kami adalah untuk mencipta fungsi, getPowerset, yang mengira set kuasa. Kami menyasarkan untuk mencapai kerumitan masa yang terbaik untuk fungsi ini.

Penyelesaian

Kerumitan masa pengiraan set kuasa sememangnya O(2^n), di mana n adalah saiz set asal. Fungsi di bawah menggunakan generik dan set untuk melaksanakan pengiraan set kuasa dengan cekap:

public static <T> Set<Set<T>> powerSet(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 : powerSet(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}

Ujian

Kod berikut menunjukkan fungsi dengan input contoh:

Set<Integer> mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : SetUtils.powerSet(mySet)) {
    System.out.println(s);
}

Output

The output ujian, seperti yang disediakan dalam soalan, memaparkan set kuasa {1, 2, 3}:

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

Dengan melaksanakan fungsi getPowerset menggunakan generik dan rekursi, kami mencapai kerumitan masa optimum O (2^n) dan penyelesaian yang cekap untuk mengira set kuasa set dalam Java.

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