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);
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; }
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); }
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!