Bagaimana untuk Menjana Set Kuasa Set dalam Java dengan Cekap?

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>> powerSet = getPowerset(mySet);</set></integer></integer>

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>> powerSet(Set<t> originalSet) {
    Set<set>> sets = new HashSet<set>>();
    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;
}  </t></t></t></t></t></t></t></t></set></set></t></set></t>

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

Ini akan mencetak output berikut:

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

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!