Bagaimana untuk Menjana Powerset Set dalam Java dengan Cekap?

Mencari Set Kuasa dalam Java: Pendekatan Cekap

Set kuasa set merangkumi semua subset yang mungkin bagi set asal. Untuk set saiz n, set kuasa mengandungi elemen 2^n. Di Java, adalah perkara biasa untuk mengendalikan penciptaan set kuasa menggunakan algoritma yang cekap.

Pertimbangkan contoh:

Tetapkan mySet = HashSet baharu<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set> ; powerSet = getPowerset(mySet);

Dengan persediaan ini, tugasnya adalah untuk mereka bentuk fungsi getPowerset yang menjana set kuasa mySet dengan kerumitan masa yang optimum.

Kerumitan Masa Optimum: O (2^n)

Seperti yang dinyatakan, set kuasa mengandungi elemen 2^n. Oleh itu, menjana semua elemen ini sememangnya memerlukan kerumitan masa O(2^n).

Pelaksanaan

Kod berikut menawarkan pelaksanaan yang generik dan cekap:

statik awam Tetapkan> powerSet(Set 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;

}

Contoh

Menggunakan contoh yang disediakan sebelum ini:

Tetapkan mySet = HashSet baharu<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set s : powerSet(mySet)) {

System.out.println(s);

}

Outputnya ialah:

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

Ini menunjukkan penciptaan set kuasa set yang ditentukan dengan kerumitan masa O(2^n).

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