Bộ nguồn 1, 2, 3 trong python

Tập hợp lũy thừa của một tập hợp là tập hợp tất cả các tập hợp con của nó hoặc tập hợp tất cả các tổ hợp khác nhau của các phần tử có trong tập hợp đã cho đó. trong bài viết này, chúng ta sẽ khám phá ngắn gọn toán học đằng sau các tập hợp sức mạnh, rút ​​ra và so sánh ba thuật toán khác nhau được sử dụng để tạo ra chúng

bộ. lót

Để làm mới những kỷ niệm của chúng tôi. một tập hợp, khối xây dựng của lý thuyết tập hợp1, là một tập hợp gồm bất kỳ số lượng đối tượng duy nhất nào mà thứ tự của chúng không quan trọng. Một tập hợp được thể hiện bằng cách sử dụng ký hiệu dấu ngoặc, như và một tập hợp trống hoặc null, được biểu thị bằng cách sử dụng một trong hai và. Bởi vì các tập hợp không theo thứ tự, nên chúng ta có thể nói rằng và bằng nhau, và bởi vì chúng chỉ chứa các phần tử riêng biệt, nên một cái gì đó giống như không hợp lệ

tập con và tập lũy thừa

Tập hợp con của một tập hợp là bất kỳ sự kết hợp nào [bao gồm tập hợp rỗng] của các thành viên của nó, sao cho nó được chứa bên trong tập hợp lớn nhất; . Nếu một tập hợp con chứa tất cả các thành viên của tập hợp cha mẹ [nghĩa là đó là một bản sao], chúng tôi gọi nó là một tập hợp con không chính xác - nếu không, nó đúng. Cuối cùng, lũy thừa của một tập hợp là tập hợp tất cả các tập con của nó, vì vậy lũy thừa của một tập hợp là

cardinality của một bộ sức mạnh

Độ dài, hay lực lượng, của một tập hợp lũy thừa là , trong đó lực lượng của tập ban đầu, do đó, số lượng tập hợp con của một tập hợp giống như là 8. Hai cách chứng minh tài sản đó một cách không chính thức

1. khi tạo một tập hợp con của một tập hợp nhất định, chúng tôi lặp lại các phần tử của tập hợp đã cho và chọn xem mỗi phần tử sẽ nằm trong tập hợp con đó hay không. Vì có 2 kết quả có thể xảy ra cho mỗi lựa chọn [phần tử được chọn hoặc không được chọn] và có các phần tử nên phải có các tập hợp con
2. khi thêm một phần tử vào một tập hợp, để cập nhật tập hợp sức mạnh của nó, bạn phải tạo một bản sao của từng tập hợp con hiện có của nó với phần tử mới được bao gồm. Chúng tôi sẽ sử dụng điều này để thực hiện thuật toán thứ hai ngắn gọn của chúng tôi

Ghi chú. các thuật toán sau được kèm theo triển khai Python. Để đơn giản hóa mọi thứ và vì các thuật toán không phụ thuộc vào ngôn ngữ, tôi đã tránh sử dụng các hàm dựng sẵn dành riêng cho Python [như yield] và các hàm [như list.extend[]] không có từ tương đương rõ ràng trong hầu hết các ngôn ngữ khác, mặc dù chúng sẽ' . Ngoài ra, mặc dù chúng tôi đang xử lý các tập hợp, chúng tôi sẽ sử dụng danh sách [mảng] với giả định rằng chúng chứa các phần tử riêng biệt

Đây là cú đâm đầu tiên của tôi vào một thuật toán, được cung cấp một tập hợp, trả về tập hợp sức mạnh của nó và thật bất ngờ. Đó là cách ít trực quan nhất và không trang nhã nhất trong ba. Chúng ta bắt đầu bằng cách viết một hàm đệ quy k_subsets[] để tìm tất cả các tập hợp con của một tập hợp có số lượng [a. k. a. -tập con của nó]

tạo tập con k

1. Đưa ra một tập hợp độ dài và một tập hợp con mong muốn của độ dài, lặp lại các phần tử đầu tiên
2. Đối với mỗi phần tử, thực hiện một cuộc gọi đệ quy để truy xuất các -subsets cho phần còn lại của mảng [tất cả các phần tử sau phần tử hiện tại]
3. Nối phần tử vào mỗi -subset và trả về các tập hợp con này

def k_subsets[k, set_]:
    if k == 0:
        return [[]]
    else:
        subsets = []
        for ind in xrange[len[set_] - k + 1]:
            for subset in k_subsets[k - 1, set_[ind + 1:]]:
                subsets.append[subset + [set_[ind]]]
        return subsets

từ k-tập con đến tập lũy thừa

Với khả năng tạo bất kỳ -subset nào, chìa khóa để tạo một power set là tìm các -subset cho tất cả các valid , nằm trong phạm vi [, một lần nữa, là lực lượng của superset]

1. Đối với bất kỳ trong
2. tìm tập hợp con -subsets

Chúng tôi sẽ giới thiệu một hàm bao bọc, power_set[], trong đó chúng tôi sẽ lồng một k_subsets[] được sửa đổi một chút để tận dụng các bao đóng

def power_set_1[set_]:
    def k_subsets[k, start_ind]:
        if k == 0:
            return [[]]
        else:
            subsets = []
            for ind in xrange[start_ind, len[set_] - k + 1]:
                for subset in k_subsets[k - 1, ind + 1]:
                    subsets.append[subset + [set_[ind]]]
            return subsets

    subsets = []
    for k in xrange[len[set_] + 1]:
        for subset in k_subsets[k, 0]:
            subsets.append[subset]
    return subsets

Thuật toán thứ hai dựa trên bằng chứng không chính thức thứ hai của chúng tôi về lực lượng của tập hợp. bất cứ khi nào một phần tử được thêm vào một tập hợp, nó phải được thêm vào các bản sao của tất cả các tập hợp con trong tập sức mạnh hiện tại của nó để tạo thành tập hợp mới. Như vậy

1. Bắt đầu với một tập rỗng, , và tập sức mạnh của nó,
2. Đối với mọi phần tử bên trong superset
3. Tạo một bản sao của mọi bộ trong bộ sức mạnh hiện tại
4. Thêm phần tử vào mỗi cái
5. Thêm các bản sao vào bộ nguồn hiện tại

như vậy

def power_set_2[set_]:
    subsets = [[]]
    for element in set_:
        for ind in xrange[len[subsets]]:
            subsets.append[subsets[ind] + [element]]
    return subsets

Thuật toán thứ ba là một cách hack thông minh và dựa vào biểu diễn nhị phân của một số tăng dần để xây dựng các tập hợp con. Trong bằng chứng đầu tiên của chúng tôi về tính chính yếu của một tập hợp sức mạnh, chúng tôi đã lặp lại từng phần tử của một tập hợp đối số và đưa ra lựa chọn với hai kết quả có thể xảy ra [phần tử đó là hoặc không phải là thành viên của tập hợp con]. . Hãy xem xét một số nguyên của -bits. nó có các giá trị có thể có trong phạm vi , nghĩa là chúng ta có thể sử dụng nó để thể hiện sự sắp xếp riêng biệt của các bit. Hừm…

1. Lặp lại trên phạm vi
2. Đối với mọi giá trị, hãy kiểm tra từng bit của nó
3. Nếu bit thứ có giá trị là 1, hãy thêm giá trị thứ của siêu tập hợp vào tập hợp con hiện tại

def is_bit_flipped[num, bit]:
    return [num >> bit] & 1

def power_set_3[set_]:
    subsets = []
    for subset in xrange[2 ** len[set_]]:
        new_subset = []
        for bit in xrange[len[set_]]:
            if is_bit_flipped[subset, bit]:
                new_subset.append[set_[bit]]
        subsets.append[new_subset]
    return subsets

1. [hoàn toàn tiếp tuyến] bất cứ khi nào tôi đề cập đến lý thuyết tập hợp, tôi không thể không nghĩ đến Principia Mathematica khét tiếng. một nỗ lực đáng kinh ngạc gồm ba tập để tiên đề hóa toàn bộ toán học, được xuất bản bởi Bertrand Russell và Alfred North Whitehead vào năm 1910-‘13, chủ yếu dựa vào các tập hợp. Nó khét tiếng, trong số những thứ khác, vì đã chứng minh không dưới 379 trang. Kiểm tra nó ra

Tập lũy thừa của A ={ 1 2 3 là bao nhiêu?

Tập lũy thừa của G ={ 1 2 3 có bao nhiêu phần tử?

Tập lũy thừa của A ={ 1 2 là bao nhiêu?

Python tính toán Powerset như thế nào?