Bộ tách rời Python
|
Tập hợp rời rạc là một cấu trúc dữ liệu theo dõi một tập hợp các phần tử được phân chia thành nhiều tập hợp con rời rạc (không chồng chéo). Nói cách khác, một tập hợp rời rạc là một nhóm các tập hợp trong đó không có phần tử nào có thể nằm trong nhiều hơn một tập hợp. Nó còn được gọi là cấu trúc dữ liệu hợp-tìm vì nó hỗ trợ thao tác hợp và tìm trên các tập con. Hãy bắt đầu bằng cách xác định chúng Show Tìm. Nó xác định phần tử cụ thể nằm trong tập hợp con nào và trả về đại diện của tập hợp cụ thể đó. Một mục từ bộ này thường đóng vai trò là "đại diện" của bộ. Liên minh. Nó hợp nhất hai tập hợp con khác nhau thành một tập hợp con duy nhất và đại diện của tập hợp này trở thành đại diện của tập hợp khác. Tập hợp rời rạc cũng hỗ trợ một thao tác quan trọng khác có tên là MakeSet , tạo một tập hợp chỉ chứa một phần tử đã cho trong đó. Union–Find hoạt động như thế nào?Chúng ta có thể xác định xem hai phần tử có thuộc cùng một tập con hay không bằng cách so sánh kết quả của hai thao tác Tìm. Nếu hai phần tử thuộc cùng một tập hợp thì chúng có cùng cách biểu diễn; . Nếu hợp được gọi trên hai phần tử, hợp nhất hai tập hợp con mà hai phần tử đó thuộc về Làm thế nào để thực hiện các bộ rời rạc?Rừng tập hợp rời rạc là cấu trúc dữ liệu trong đó mỗi tập hợp được biểu thị bằng một dữ liệu dạng cây trong đó mỗi nút chứa tham chiếu đến cha của nó và đại diện của mỗi tập hợp là gốc của .
Ví dụ, xem xét năm tập hợp khác nhau
Phép toán  Nếu chúng ta thực hiện
Nếu chúng ta thực hiện
Nếu chúng ta thực hiện
Một cách để thực hiện những điều này có thể là function MakeSet(x) Sau đây là triển khai C++, Java và Python của union–find sử dụng bảng băm để triển khai một tập hợp rời rạc C++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 #include #include #include sử dụng không gian tên std;
// Một lớp đại diện cho một tập hợp rời rạc lớp DisjointSet { unordered_map<int, int> parent;
công khai.
// thực hiện thao tác MakeSet void makeSet(vector<int> const &universe) { // tạo `n` bộ rời rạc (mỗi bộ một mục) cho (int i: vũ trụ) { cha mẹ[i] = i; } }
// Tìm gốc của tập hợp chứa phần tử `k` int Tìm(int k) { // nếu `k` là gốc nếu (cha mẹ[k] == k) { return k; }
// lặp lại cho cấp độ gốc cho đến khi chúng tôi tìm thấy thư mục gốc trả về Tìm(cha[k]); }
// Thực hiện phép hợp hai tập con vô hiệu Liên minh(int a, int b) { // tìm nghiệm của tập hợp chứa các phần tử `x` và `y` int x = Tìm(a); int y = Tìm(b);
cha mẹ[x] = y; } };
void printSets(vectơ<int> const &universe, DisjointSet &ds) { cho (int i: vũ trụ) { cout << ds. Tìm(i) < " "; } cout << endl; }
// Cấu trúc dữ liệu Disjoint–Set (thuật toán Union–Find) int chính() { // nhiều mặt hàng vectơ<int> universe = { 1, 2, 3, 4, 5 };
// khởi tạo lớp `DisjointSet` DisjointSet ds;
// tạo một tập hợp đơn lẻ cho từng phần tử của vũ trụ ds. makeSet(vũ trụ); printSets(vũ trụ, ds);
ds. Liên minh(4, 3); // 4 and 3 are in the same set printSets(vũ trụ, ds);
ds. Liên minh(2, 1); // 1 and 2 are in the same set printSets(vũ trụ, ds);
ds. Liên minh(1, 3); // 1, 2, 3, 4 are in the same set printSets(vũ trụ, ds);
return 0; } Tải xuống Chạy mã Đầu ra. Java1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 nhập java. sử dụng. HashMap; nhập java. sử dụng. Bản đồ;
// Một lớp đại diện cho một tập hợp rời rạc lớp DisjointSet { riêng tư Bản đồ<Số nguyên, Integer> parent = new HashMap<>();
// thực hiện thao tác MakeSet công khai vô hiệu makeSet(int[] universe) { // tạo `n` bộ rời rạc (mỗi bộ một mục) cho (int i: vũ trụ) { cha mẹ. đặt(i, i); } }
// Tìm gốc của tập hợp chứa phần tử `k` công khai int Tìm(int k) { // nếu `k` là gốc nếu (cha mẹ. nhận(k) = k) { return k; }
// lặp lại cho cấp độ gốc cho đến khi chúng tôi tìm thấy thư mục gốc trả về Tìm(cha.nhận(k)); }
// Thực hiện phép hợp hai tập con công khai vô hiệu Liên minh(int a, int b) { // tìm nghiệm của tập hợp chứa các phần tử `x` và `y` int x = Tìm(a); int y = Tìm(b);
cha mẹ. đặt(x, y); } }
lớp Chính { công khai tĩnh vô hiệu printSets(int[] universe, DisjointSet ds) { cho (int i: vũ trụ) { Hệ thống. ra. in(ds. Tìm(i) + " "); }
Hệ thống. ra. println(); }
// Cấu trúc dữ liệu Disjoint–Set (thuật toán Union–Find) công khai tĩnh vô hiệu chính(String[] args) { // nhiều mặt hàng int[] vũ trụ = { 1, 2, 3, 4, 5 };
// khởi tạo lớp `DisjointSet` DisjointSet ds = mới DisjointSet();
// tạo một tập hợp đơn lẻ cho từng phần tử của vũ trụ ds. makeSet(vũ trụ); printSets(vũ trụ, ds);
ds. Liên minh(4, 3); // 4 and 3 are in the same set printSets(vũ trụ, ds);
ds. Liên minh(2, 1); // 1 and 2 are in the same set printSets(vũ trụ, ds);
ds. Liên minh(1, 3); // 1, 2, 3, 4 are in the same set printSets(vũ trụ, ds); } } Tải xuống Chạy mã Đầu ra. con trăn1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 # Một lớp đại diện cho một tập hợp rời rạc lớp DisjointSet. cha mẹ = {}
# thực hiện thao tác MakeSet def makeSet(self, universe): # tạo `n` bộ rời nhau (mỗi bộ một mục) vì i trong vũ trụ: bản thân. cha mẹ[i] = i
# Tìm gốc của tập hợp chứa phần tử `k` def Tìm(bản thân, k): # nếu `k` là gốc nếu chính mình. cha mẹ[k] = . k: return k # lặp lại cho cấp độ gốc cho đến khi chúng tôi tìm thấy thư mục gốc trả về chính mình. Tìm(chính mình. cha mẹ[k])
# Thực hiện phép hợp hai tập hợp con def Liên minh(bản thân, a, b): # tìm gốc của các tập hợp chứa phần tử # `x` và `y` thuộc về x = bản thân. Tìm(a) y = chính mình. Tìm(b)
bản thân. cha mẹ[x] = y
def printSets(vũ trụ, ds): in([ds.Tìm(i) cho i in universe])
# Cấu trúc dữ liệu Disjoint–Set (thuật toán Union–Find) if __name__ == '__main__'.
# mặt hàng vũ trụ = [1, 2, 3, 4, 5]
# khởi tạo tập rời rạc ds = DisjointSet()
# tạo một tập hợp đơn lẻ cho từng phần tử của vũ trụ ds. makeSet(vũ trụ) printSets(vũ trụ, ds)
ds. Liên minh(4, 3) # 4 and 3 are in the same set printSets(vũ trụ, ds)
ds. Liên minh(2, 1) # 1 and 2 are in the same set printSets(vũ trụ, ds)
ds. Liên minh(1, 3) # 1, 2, 3, 4 are in the same set printSets(vũ trụ, ds)
Tải xuống Chạy mã Đầu ra. Cách tiếp cận trên không tốt hơn cách tiếp cận danh sách liên kết vì cây mà nó tạo ra có thể rất mất cân bằng; 1. Cách thứ nhất, được gọi là liên kết theo thứ hạng , là luôn gắn cây nhỏ hơn vào gốc của cây lớn hơn. Vì độ sâu của cây ảnh hưởng đến thời gian chạy, nên cây có độ sâu nhỏ hơn được thêm vào dưới gốc của cây sâu hơn, điều này chỉ làm tăng độ sâu của các độ sâu bằng nhau. Các cây một phần tử được định nghĩa là có thứ hạng bằng 0 và bất cứ khi nào hai cây có cùng thứ hạng 2. Cải tiến thứ hai, được gọi là nén đường dẫn , là một cách làm phẳng cấu trúc của cây bất cứ khi nào Find được sử dụng trên đó. Ý tưởng là mỗi nút được truy cập hướng đến nút gốc cũng có thể được gắn trực tiếp vào nút gốc; . Để thực hiện điều này, khi Find duyệt qua cây một cách đệ quy, nó sẽ thay đổi tham chiếu gốc của mỗi nút để trỏ đến gốc được tìm thấy. Cây kết quả phẳng hơn nhiều, tăng tốc các hoạt động trong tương lai không chỉ trên các phần tử này mà còn trên các phần tử tham chiếu đến chúng, trực tiếp hoặc gián tiếp. function MakeSet(x) Hai kỹ thuật này bổ sung cho nhau và thời gian chạy trên mỗi thao tác thực sự là một hằng số nhỏ. Thuật toán có thể được triển khai như sau trong C++, Java và Python rời rạc là gìTập rời rạc là gì? . Ví dụ: tập hợp A={2,3} và tập hợp B={4,5} là các tập hợp rời nhau. Nhưng tập hợp C={3,4,5} và {3,6,7} không rời nhau vì cả tập hợp C và D đều có 3 là phần tử chung. Tìm hiểu thêm về Disjoint Set tại đây. A pair of sets which does not have any common element are called disjoint sets. For example, set A={2,3} and set B={4,5} are disjoint sets. But set C={3,4,5} and {3,6,7} are not disjoint as both the sets C and D are having 3 as a common element. Learn more about Disjoint Set here.
Các tập hợp A và B có phải là Python không?Phương thức isdisjoint của python sẽ giúp chúng ta tìm ra các tập hợp đã cho có phải là các tập hợp rời rạc hay không. A và B là các tập hợp rời nhau vì cả hai tập hợp không có phần tử chung.
Hợp rời rạc của hai tập hợp là gì?Liên kết rời của hai tập hợp và là toán tử nhị phân kết hợp tất cả các phần tử riêng biệt của một cặp tập hợp đã cho, trong khi vẫn giữ nguyên thuộc tính của tập ban đầu như một đặc điểm phân biệt của liên kết . .
Hai tập hợp rỗng có rời nhau không?Nhắc lại định nghĩa rời rạc. Hai tập hợp là rời nhau nếu giao của chúng trống. Lưu ý rằng giao của tập hợp rỗng với bất kỳ tập hợp nào là rỗng. Do đó, tập hợp rỗng tách biệt với mọi tập hợp |
