Rumah > Java > javaTutorial > Bagaimana untuk Menjana Set Kuasa Set dalam Java dengan Cekap?

Bagaimana untuk Menjana Set Kuasa Set dalam Java dengan Cekap?

Linda Hamilton
Lepaskan: 2024-12-14 22:41:14
asal
252 orang telah melayarinya

How to Efficiently Generate the Power Set of a Set in Java?

Menjana Set Kuasa Set dalam Java

Set kuasa set ialah set semua subset set itu. Contohnya, set kuasa {1, 2, 3} ialah:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3} , {1, 2, 3}, {1}}

Andaikan kita mempunyai Set dalam Java:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
Salin selepas log masuk

Bagaimana kita boleh menulis fungsi getPowerset dengan kerumitan masa yang optimum?

Penyelesaian

Kerumitan masa bagi fungsi set kuasa ialah O(2^n), dengan n ialah bilangan elemen dalam set. Ini kerana set kuasa set dengan n elemen mengandungi 2^n subset.

Berikut ialah pelaksanaan fungsi getPowerset yang berfungsi menggunakan generik dan set:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}  
Salin selepas log masuk

Ujian

Mari kita uji fungsi getPowerset dengan contoh yang diberikan input:

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

Ini akan mencetak output berikut:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
Salin selepas log masuk

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

sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan